time-complexity - 分析通用算法的复杂性

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 个 block 来存储 n 个元素(对吗？？)这是分析运行时间和空间复杂度的正确方法吗？我可以分析常见排序算法和数据结构的时间复杂度，但我在分析一般程序时遇到了一些困难。谢谢!!

Answer 1

随着 n 的增长，这将是 O(n^2) n^2 将使 O(n) 部分相形见绌，因此该部分将被淘汰。例如，当 n 为 100 时。第一个操作将花费 100 个单位的时间，第二个操作将花费 10,000 个单位的时间。 99% 的计算时间将花在第二次操作上。随着 n 的增加，第二个操作将继续占主导地位。我认为没有理由不是 O(n) 空间复杂度。