时间复杂度计算

时间复杂度计算

解释

• O(1)：常数时间复杂度，表示算法的执行时间不随输入数据的大小变化而变化。
• O(log n)：对数时间复杂度，表示算法的执行时间按对数速率增加，这通常是非常有效的，例如二分查找算法。
• O(n)：线性时间复杂度，表示算法的执行时间与输入数据的大小成正比。
• O(n log n)：线性对数时间复杂度，比线性时间稍慢，常见于某些高效的排序算法，如快速排序和归并排序。
• O(n^2)：二次时间复杂度，表示算法的执行时间与输入数据的平方成正比，常见于简单的排序算法，如冒泡排序和插入排序。
• O(2^n)：指数时间复杂度，表示算法的执行时间以指数方式增加，这在输入数据稍大时通常是不切实际的。
• O(n!)：阶乘时间复杂度，表示算法的执行时间随输入数据的阶乘增加，通常是最慢的。

O(1)

let i = 0;
i += 1

O(n)

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

O(1) + O(n) = O(n)

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

O(n) * O(n) = O(n^2)

for (let i = 0; i < n; i += 1) {
    for (let j = 0; j < n; j += 1) {
        console.log(i, j)
    }
}

O(logN)

let i = 1;
while (i < n) {
    console.log(i);
    i *= 2;
}

• 维基百科，自由的百科全书