时间复杂度

1. 用常数1取代运行期间中所有加法常数
2. 修改后的运行次数函数中，仅保留最高阶项
3. 如果最高阶项存在且不是1，则去除与该项相乘的常数
4. 得出结果

从一个代码片段我们一般关注几个点：

• 循环的退出条件，变量是如何趋近于这个退出条件的

• 循环体的嵌套，应用的是乘法原则

• 循环体并列，应用加法原则

1
2
3
4
5

int func(int n) {
    int i = 0,sum = 0;
    while(sum<n) sum+=++i; //关注退出条件，变量每次执行怎么变
    return i			//这实际上就是个公差为1的等差数列
}

空间复杂度

如果输入的数据所占空间仅取决于问题本身，与算法无关，则只需分析除输入和程序之外的额外空间。

算法原地工作即指算法无需额外辅助空间，即O(1)