如何计算此特定算法的时间复杂度？

Question

我知道还有很多其他问题要求如何计算时间复杂度的一般指南，例如 one。

从他们那里我了解到，当有一个循环时，例如我的 Python 程序中的 (for... if...) ，时间复杂度是 N * N ，其中 N 是输入的大小。（如果这也错了请指正）（被答案更正后编辑一次）

# greatest common divisor of two integers 

a, b = map(int, input().split())
list = []

for i in range(1, a+b+1):
  if a % i == 0 and b % i == 0:
    list.append(i) 

n = len(list)
print(list[n-1])

但是，代码的其他部分是否也会增加时间复杂度，这将使其不仅仅是简单的 O(n) = N^2 ？例如，在我寻找 a 和 b (a%i = 0) 的公约数的第二个循环中，有没有办法知道计算机在寻找所有公约数时将执行多少条机器指令，以及随之而来的时间复杂度，在这个特定的循环中？

我希望这个问题是有道理的，如果不够清楚，请道歉。

感谢您的回答

Answer 1

要记住的一件事是高学历优先。所以你可以有一个常数 O(1) 但发生 n 次 O(N) 那么它将是 O(1) * O(N) = O(N).

你的程序是 O(N)，因为唯一真正影响时间复杂度的是循环，正如你所知，像这样的简单循环是 O(N)，因为它随着 n 的增加而线性增加。

现在，如果您有一个嵌套循环，其中两个循环都随着 n 的增加而增加，那么它将是 O(n^2)。

Answer 2

首先，一些提示：

您的代码中没有嵌套循环。 if-语句不构成循环。
并非所有嵌套循环都具有二次时间复杂度。
写O(n) = N*N没有任何意义：什么是n，什么是N？为什么左边是n，右边是N？你应该期望你的时间复杂度函数依赖于你的算法的输入，所以首先定义相关的输入是什么以及你给它们起什么名字。
此外，O(n) 是一个集函数（即那些由函数 f(n) = n 从上方渐进界定的函数，而 f(N) = N*N 是一个函数。由于滥用符号，我们通常将n*n = O(n)写成n*n ∈ O(n)（这在数学上是错误的陈述），但换边（O(n) = n*n) 未定义。数学上正确的陈述是 n = O(n*n).
您可以假设所有（固定位长）算术运算都是 O(1)，因为所需的处理器指令数有一个恒定的上限。处理器指令的确切数量与分析无关。

让我们更详细地看一下代码并对其进行注释：

a, b = map(int, input().split()) # O(1)
list = []                        # O(1)

for i in range(1, a+b+1):        # O(a+b) multiplied by what's inside the loop
  if a % i == 0 and b % i == 0:  # O(1)
    list.append(i)               # O(1) (amortized)

n = len(list)                    # O(1)
print(list[n-1])                 # O(log(a+b))

那么整体的复杂度是多少？占主导地位的部分确实是循环（前后的东西可以忽略不计，复杂性），所以它是 O(a+b)，如果你把 a 和 b 作为输入参数。（如果您想将输入 input() 的长度 N 作为输入参数，它将是 O(2^N)，因为 a+b 相对于 [=14] 呈指数增长=].)

如何计算此特定算法的时间复杂度？

How do I calculate Time Complexity for this particular algorithm?

python

algorithm

time-complexity