这个语句的时间复杂度怎么计算的

这个语句的时间复杂度怎么计算的,r++语句在编译器运行了21次

img

外层表示循环躺数q+1趟,内层第一趟运行q+1次第二趟q次直到第q+1趟的时候是1次, 运算次数是一个等差数列 最后总和为(q²+3q+2)/2 而时间复杂度表达的是一个变化趋势,q无限大时,低阶常数和系数影响都不大可以去掉最后 q看作n 时间复杂度是o(n²)

O(N^2)

1.首先,这是一个二重循环
2.外层循环次数是q,复杂度O(n)
3.内层很显然跟i有关,i越大次数越小,那么最终形成一个三角形,三角形面积公式底乘以高除以2,所以是n^2/2次
4.计算复杂度的时候不要系数和常数项,把1/2消掉,那么答案就是O(n^2)