关于程序的时间复杂性

Question

我在一次竞争性考试中做了一道题，但我正在努力找出程序的时间复杂性，即在Python3中是O（n）还是O（n^2）。有人能帮我吗

我问了我的一个朋友，他们中的一些告诉我这是O（n^2），他们中的一些告诉我这是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

在哪里

n = len(s) m = len(b)

您的代码将随时间复杂度而扩展

O(m*n)

因为在最坏的情况下，您将遍历整个基字符串并执行m最大恒定时间if操作。N在理论上通常用作占位符，但对于代码没有任何意义

Answer 2

根据我的经验，这里的误解在初学者中很常见，就是big-O符号中只能有一个变量。这似乎是因为大多数介绍性示例都是用一个输入来显示的。当您有多个独立的输入时，您可以有多个变量，因为当其中一个输入发生变化时，复杂性将独立地扩展

一个普遍存在的例子就是图形。图有节点和边。节点数可能会设置边数的上限，但这两者实际上是相当独立的。因此，大多数图算法是根据V和E来分析的，而不是单个变量N

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