数据结构的时间复杂度问题

Question

for(i=1;i<=n;i++)
    for(j=1;j<=i;j++)
        for(k=1;k<=j;k++)
            x++;

请问这个代码的时间复杂度n^3是如何计算的

Answer 1

i执行次数是n
j<i，那么其实就是个三角形，执行次数n^2/2
k<j，那么就是个三棱锥，执行次数n^3/6
这里的1/6是系数，在问复杂度问题的时候系数和常数项都被忽略，只保留n的最高次幂
所以就是O(n^3)