算法效率分析#

时间复杂度(Time Complexity)#

时间复杂度是衡量算法执行时间随输入规模变化的函数。常见的时间复杂度表示法包括大O符号（Big O notation），它描述了算法在最坏情况下的增长率。常见的时间复杂度有：

• O(1)：常数时间复杂度，表示算法的执行时间不随输入规模变化。
• O(log n)：对数时间复杂度，表示算法的执行时间随着输入规模的对数增长。
• O(n)：线性时间复杂度，表示算法的执行时间与输入规模成正比。
• O(n log n)：线性对数时间复杂度，常见于高效排序算法如归并排序和快速排序。
• O(n^2)：平方时间复杂度，常见于简单排序算法如冒泡排序和插入排序。
• O(2^n)：指数时间复杂度，表示算法的执行时间随着输入 规模的指数增长，通常不可行用于大规模输入。

实际上，算法的时间复杂度可以通过分析其基本操作的执行次数来确定。通常，我们关注的是最耗时的部分，因为它决定了整体的时间复杂度。例如：

1
for (int i = 0; i < n; i++) { // O(n)
2
    for (int j = 0; j < n; j++) { // O(n)
3
        // 常数时间操作 O(1)
4
        // 1 Unit of work time
5
    }
6
}

在上述代码中，外层循环执行n次，内层循环也执行n次，因此总的时间复杂度为O(n^2)。 在数学上看，我们一般只看增长的最快的那部分，所以虽然里面有i = 0 等等的实际上也耗费时间的操作，但它们相对于j < n这些增长更快的操作来说是可以忽略的。