在谈论时间复杂度时,我们通常使用n作为输入,这并不是对实际输入大小的精确度量。我无法证明,当对输入(s)使用特定大小时,算法保持在相同的复杂度类中。
例如,采用一个简单的顺序搜索算法。在最坏的情况下,它需要 W(n) 时间。如果我们应用特定的输入大小(以 2 为底),则顺序应该是 W(lg L),其中 L 是最大整数。
我如何证明顺序搜索或任何算法保持相同的复杂性类别,在这种情况下是线性时间? 我知道需要进行某种替代,但我对如何得出结论感到不安。
编辑
我想我可能已经找到了我正在寻找的东西,但我并不完全确定。
如果将最坏情况的时间复杂度定义为 W(s),即输入大小为 s 的算法完成的最大步数,则根据输入大小的定义,s = lg n,其中 n 是输入。那么,n = 2^s,得出时间复杂度为W(2^s),指数复杂度的结论。因此,二进制编码的算法性能是指数的,而不是线性的,因为它在数量级上。