这个伪代码的运行时复杂度是多少？

Question

我无法理解伪代码的时间复杂度。

p=10; 
num=0; 
plimit=100000; 
    for (i = p; i<=plimit; i++) 
     for (j = 1; j<=i; j++) 
      num = num + 1; 

我认为这将是一个线性搜索，但只是想确认。

Answer 1

这不是线性时间。由于(n+1)*(n/2)因为1 + 2 + 3 ... + n会给你O（n ），所以内循环具有增量运算成本。