python - 关于程序的时间复杂度

Question

我在一项竞争性考试中完成了问题，但我正在努力找出程序的时间复杂度，即它是O(n) 还是 O(n^2) 在 python 3 中。任何人都可以帮助我。

我问了我的一个 friend ，他们中的一些人告诉它是 O(n)，而他们中的一些人告诉它是 O(n^2)，所以我完全对这些答案感到困惑。

s = input() #reading base string
b = input() #reading reference string
for i in s:
    if i in b:
        print(i, end='')

示例输入:

 polikujmnhytgbvfredcxswqaz  #base string
 abcd  #refernce string

示例输出:

 bdca

Answer 1

根据我的经验，这里的误解是初学者中很常见，即大 O 表示法中只能有一个变量。这似乎会发生，因为大多数介绍性示例都是使用单个输入显示的。当您有多个独立输入时，您可以有多个变量，因为当任一输入发生变化时，复杂性将独立缩放。

图表就是一个常见的例子。图有节点和边。节点的数量可能会设定边的数量的上限，但两者实际上是相当独立的。因此，大多数图算法都是根据 V 和 E 进行分析，而不是单个变量 N。

这对您来说意味着您有两个独立的数量。假设S = len(s) 和B = len(b)。外层循环执行 S 次迭代。运算符in b 在最坏的情况下执行B 操作。如果您假设 print 在恒定时间内运行单个字符，则结果为 O(S * B)。