如何获取不同更新索引方式的whilefor循环的复杂度顺序？

Question

我在查简单的复杂度顺序问题，发现了这个问题。

int example(int max) {
    int i  =  0;
    double x  =  0.0;

    while ( i <= max ) {
        x  =  doStuff(x , i); //doStuff is O(i)
        i  = i + 10 ;
    }
}

我们知道 doStuff(int x, int i) 是 O(i)例子的顺序应根据以下情况而定 max.

现在，我已经看到并理解了循环运行在 O(i),O(log i)等......但我怎样才能得到while循环的顺序（从而得到了 example)，当被检查的索引和传递给函数的索引的总和确实比其他通常的 i++ 或 2*i?

Answer 1

该案例 i = i + 10 不相上下 i++:

整个算法的复杂程度顺序是（其中 / 是整数除法，而 m 是 max):

        O(0)+O(10)+O(20)+.。+ O((m10)*10)

作为 O(x)+O(y)=O(x+y)，我们可以写成。

        O(10(1+2+3+... +m10))

而我们可以应用通常的公式来计算 三角形数:

        O(10(m10)(m10 - 1)2)

我们只需要最高阶的项，可以忽略其系数。

        = O(m²)