定义

若存在函数 f（n），使得当n趋近于无穷大时，T（n）/ f（n）的极限值为不等于零的常数，则称 f（n）是T（n）的同数量级函数。

记作 T（n）= O（f（n）），称O（f（n）） 为算法的渐进时间复杂度。也叫大O表示法。

推导原则

• 用常数1取代运行时间中的所有加法常数；

• 在修改后的运行次数函数中，只保留最高阶项；

• 如果最高阶项存在且不是1，则去除与这个项相乘的常数。

举例

例1

for (let i = 0; i < n; i++) {
    ...
}

循环次数为 n，时间复杂度为 O(n × 1)，即 O(n)

例2

for (let i = 0; i < 5; i++) {
    for (let j = 0; j < n; j++) {
    ...
    }
}

外循环次数为常数 5，内循环次数为n，时间复杂度为 O(5 × n)，去最高阶项前面的系数即为 O(n)

例3

for (let i = 0; i < n; i++) {
    ...
}
for (let j = 0; j < n; j++) {
    ...
}

循环次数为 n+m，最高阶项为n或者m，由规则3得到时间复杂度为O(n)

例4

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
    ...
    }
}

循环次数为 n^2,时间复杂度是O(n^2)

例5

for (let i = 0; i < n; i++) {
    for (let j = i; j < n; j++) {
    ...
    }
}

i=0时内层执行n次，i=1时内层执行n-1次，i=n-1时内层执行1次，可得f(n)=n+(n-1)+...+1=(n+1)n/2=n^2/2+n/2,保留最高项并去除常数得到时间复杂度为O(n^2)

例6

for (let i = 0; i < n; i++) {
    i*=2
}

循环次数为 log2n，时间复杂度即为O(logn)