分析通用算法的复杂性

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)时间.(这是对吗??)

空间复杂度也是O(n),因为我们在内存中有n个块来存储n个元素(这是对吗？)这是分析运行时间和空间复杂度的正确方法吗？我可以分析时间复杂度常见的排序算法和数据结构,但我只是为一般程序分析它有点困难.谢谢!!

Answer 1

这将是O(n ^ 2),因为n增长n ^ 2将使O(n)部分相形见绌,从而使部分退出.例如,当n为100.第一次操作将花费100个单位时间,第二次操作将花费10,000个单位.99%的计算时间将用于第二次操作.随着n增加,第二次操作将继续占主导地位.我认为没有理由不是O(n)空间复杂性.