O(n) 符号中 n 的可能含义？
Possible meanings of n in O(n) notation?
在问题 here 中，许多 post 人在谈论 增加 [=41] 时继续指的是 更大 输入=] n。因此，他们中的一些人说不存在复杂度为 O(1/n) 的算法。现在，假设我们有一个算法，我们通过从现有的大小为 m 的列表中删除元素来指定我们想要一个大小为 n 的列表（因此删除 m - n 元素，并且 n <= m 显然）。显然，增加 n 会减少计算时间，因为 larger n 意味着 less 操作。
n 然后 有 来指代输入的物理大小（如排序中输入列表的大小algorithm) 还是可以像这里一样更抽象地定义？
我知道大 O 符号是为渐近行为定义的，但是如果我们有一个算法，其中参数 n 与上面的参数有明确的界限，就像这里一样？我们可以说我们假设 n < m?
我知道上面的例子很愚蠢，但我实际上有一个案例（对于 post 这里太复杂了，因此是愚蠢的例子，但它与这个例子有一些相似之处）计算时间随着 n 的增加而明显减少，并且 n 也是从上面有界的，并且以不同的方式定义它使得它不受上面的限制是不可能的.
提前致谢
在您的示例中，您会说算法的 运行 时间是 O(m-n)（或者 O(log(m-n)) 或 O((m-n)^2)，具体取决于如何删除每个项目），以便您可以以有用的方式实际传达复杂性。可能有一种方法可以重新构建您的问题来执行此操作。符号的全部要点是简明地表达算法的可扩展性。我希望你能找到问题的各种参数的一些函数，它表达了输入的 'difficulty'（例如 m-n），这可能比大小更抽象，然后是那个难度的函数（例如 x^2) 将难度转换为 space 或时间要求。
我将使用常规符号来重新演示您的示例。我们想要一个大小为 k 的列表，方法是从现有的大小为 n 的列表中删除元素。在这个例子中，k 与 n 不同，因为 n 是输入大小，而 k 只是一个参数。
根据实现的不同，这个问题可以在 O(k) 或 O(n-k) 中完成。如果是 O(n-k) 实现，输入大小的增加仍然会导致更高的复杂性。如果是 O(k)，则算法的复杂性仅取决于参数而不取决于输入大小。无论哪种方式，您的输入大小都不会归因于算法复杂性的降低。
是的，有些算法的复杂性仅取决于参数 k，而不取决于输入大小 n，前提是我们知道参数 k 是什么（或者它可以在很短的时间内计算出来）。它广泛用于解决 NP 完全问题。 Parameterized complexity
但是，我仍然不知道任何复杂度为 O(1/n) 的算法，其中 n 是输入的大小。
在问题 here 中，许多 post 人在谈论 增加 [=41] 时继续指的是 更大 输入=] n。因此，他们中的一些人说不存在复杂度为 O(1/n) 的算法。现在，假设我们有一个算法，我们通过从现有的大小为 m 的列表中删除元素来指定我们想要一个大小为 n 的列表（因此删除 m - n 元素，并且 n <= m 显然）。显然，增加 n 会减少计算时间，因为 larger n 意味着 less 操作。
n 然后 有 来指代输入的物理大小（如排序中输入列表的大小algorithm) 还是可以像这里一样更抽象地定义？
我知道大 O 符号是为渐近行为定义的，但是如果我们有一个算法，其中参数 n 与上面的参数有明确的界限，就像这里一样？我们可以说我们假设 n < m?
我知道上面的例子很愚蠢，但我实际上有一个案例（对于 post 这里太复杂了，因此是愚蠢的例子，但它与这个例子有一些相似之处）计算时间随着 n 的增加而明显减少，并且 n 也是从上面有界的，并且以不同的方式定义它使得它不受上面的限制是不可能的.
提前致谢
在您的示例中，您会说算法的 运行 时间是 O(m-n)（或者 O(log(m-n)) 或 O((m-n)^2)，具体取决于如何删除每个项目），以便您可以以有用的方式实际传达复杂性。可能有一种方法可以重新构建您的问题来执行此操作。符号的全部要点是简明地表达算法的可扩展性。我希望你能找到问题的各种参数的一些函数，它表达了输入的 'difficulty'（例如 m-n），这可能比大小更抽象，然后是那个难度的函数（例如 x^2) 将难度转换为 space 或时间要求。
我将使用常规符号来重新演示您的示例。我们想要一个大小为 k 的列表，方法是从现有的大小为 n 的列表中删除元素。在这个例子中，k 与 n 不同，因为 n 是输入大小，而 k 只是一个参数。
根据实现的不同，这个问题可以在 O(k) 或 O(n-k) 中完成。如果是 O(n-k) 实现，输入大小的增加仍然会导致更高的复杂性。如果是 O(k)，则算法的复杂性仅取决于参数而不取决于输入大小。无论哪种方式，您的输入大小都不会归因于算法复杂性的降低。
是的，有些算法的复杂性仅取决于参数 k，而不取决于输入大小 n，前提是我们知道参数 k 是什么（或者它可以在很短的时间内计算出来）。它广泛用于解决 NP 完全问题。 Parameterized complexity
但是，我仍然不知道任何复杂度为 O(1/n) 的算法，其中 n 是输入的大小。