数据结构_知识点_算法基础

推导大O阶方法

1. 用常数1取代所运行时间中的所有加法常数
2. 在修改后的运行次数函数中，只保留最高阶项
3. 如果最高阶存在且不是1，则去除与这个项的系数

例子：

---

int i,j; for(i = 0; i < n; i++) { for(j = i; j < n; j++) { /*时间复杂度为O(1)的程序步骤序列*/ } }

f(n) = n^2/2 + n/2
只保留最高阶n^2/2，去除最高阶系数
所以O(f(n)) = O(n^2)

常见时间复杂度

<br />

Paste_Image.png

<br />
常用的时间复杂度所耗费的时间从小到大依次是：

Paste_Image.png