时间复杂度推导

定义

若存在函数 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)

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注