在问题AA>中，许多海报在提到增加N时继续引用更大的输入，因此，有些人认为O（1／N）复杂度的算法不能存在。现在，让我们假设我们有一个算法，我们通过从现有的m个列表中删除元素（因此移除M -N元素，并且明显地n那么，n是否必须引用输入的物理大小（比如排序算法中输入列表的大小），或者是否可以更抽象地定义为这里？
我知道大o符号是为渐近行为定义的，但是如果我们有一个算法，其中一个参数n从上面清楚地有界，就像这里一样？我们可以假设n我知道上面的例子很傻，但我实际上有一个例子（这个例子太复杂了，不能在这里发表，因此这个例子很傻，但它与这个例子有一些相似之处），计算时间明显随着n的增加而减少，n也从上面有界，并且以不同的方式定义它，这样它就不可能从上面有界。
提前谢谢
最佳答案
我将使用传统符号来重新演示您的示例。我们需要一个大小为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是输入的大小。