分析通用算法复杂度

Question

假设我有这样一个程序：

def fn(array,num):
   for i in range(0,len(array)):
     if(i==num):print i


   for i in range(o,len(array)):
     for j in range(0,i):
       if(i*j==num):print i,j

第一个循环的时间复杂度为O（n）。 第二个循环的时间复杂度为O（n * n）。

总的时间复杂度将是O（n）+ O（n ^ 2）= O（n ^ 2） 时间。（这样正确吗？）

此外，由于我们需要n个块来存储n个元素，因此空间复杂度将为O（n）。 （这样正确吗？） 这是分析运行时间和空间复杂度的正确方法吗？我可以分析常见排序算法和数据结构的时间复杂度，但对于一般程序分析它们的时间复杂度有些困难。谢谢！

- ashwin shanker

Answer 1

这将会是O(n^2)，随着n的增长，n^2将超过O(n)部分，因此该部分将被删除。例如，当n为100时。第一次操作将花费100个时间单位，第二次将花费10,000个时间单位。99%的时间用于计算第二个操作。随着n的增加，第二个操作将继续支配。我认为这不会导致O(n)空间复杂度上升。

- ford prefect