深入理解算法的时间复杂度

时间复杂度的定义

时间复杂度就是一种用来描述算法在输入规模增长时所需执行时间的度量，即描述算法运行时间随问题规模增加而增长的速度，它是对算法执行时间的上界估计，通常通过O符号表示。时间复杂度描述了算法的效率和执行速度，可以用来对比不同算法的性能。

备注:
1.时间复杂度描述的是算法在最坏情况下的运行时间。这是因为最坏情况下的时间复杂度是对算法性能的上界估计，能够保证算法在任何情况下都能在该时间范围内完成。
2.在实际的算法分析中，通常还考虑最好情况和平均情况下的时间复杂度。最好情况是指在最理想的输入情况下的时间复杂度，平均情况是对所有可能输入情况下的平均时间复杂度的估计。

时间复杂度的分类

时间复杂度粗略的分为两类: 多项式量级和非多项式量级
非多项式量级只有两个
$$O(2^n)和O(n!)$$

非多项式量级算法的执行时间会随着输入规模的增加急剧增长，是非常低效的算法。
多项式量级的复杂度常见的并不多，从低阶到高阶有(越高阶的时间复杂度，执行效率越低):

$$O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)$$

对应的曲线图如下图所示:

时间复杂度分析

1.我们在分析一个算法、一段代码的时间复杂度的时候，只需关注循环执行次数最多的那一段代码就可以了，它就代表着这个算法的时间复杂度。
2.加法法则:多个算法顺序追加使用的时候，总复杂度等于量级最大的那段代码的复杂度
3.乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

常见数据结构和算法的时间复杂度

常见数据结构

1.数组(Array)

• 索引访问: O(1)
• 查找: O(n)
• 插入/删除(末尾): O(1)
• 插入/删除(中间或开头): O(n)

2.链表(Linked List)

• 访问: O(n)
• 查找: O(n)
• 插入/删除(在头部进行): O(1)
• 插入/删除(在中间或末尾进行): O(1)(如果已知位置)，O(n)(如果需要搜索位置)

3.栈(Stack)

• 插入/删除(在顶部): O(1)
• 访问,查找: O(n)

4.队列(Queue)

• 插入/删除(在头部或尾部进行): O(1)
• 访问: O(n)

5.哈希表(Hash Table):

• 插入/删除/访问(平均情况): O(1)
• 最坏情况下可能是O(n)，取决于哈希冲突的数量

常见算法

1.线性搜索

• 时间复杂度:O(n)

2.二分查找

• 时间复杂度:O(logn)

3.冒泡排序

• 平均情况和最坏情况: O(n^2)

4.快速排序(Quick Sort)

• 平均情况: O(nlogn)
• 最坏情况: O(n^2)

5.归并排序(Merge Sort)

• 最好情况、平均情况和最坏情况: O(nlogn)

6.堆排序(Heap Sort)

• 平均情况和最坏情况: O(nlogn)

常见排序算法说明

注: 排序算法的稳定性是指在排序过程中，具有相等键值的元素在排序后的结果中，相对顺序保持不变的性质。稳定性是排序算法中一个重要的性质，因为在某些应用场景中，我们希望保持相等元素的相对顺序不变。稳定性的好处是可以确保排序算法在特定情况下的正确性，特别是在应对某些有依赖顺序的问题时。但是，并不是所有的排序算法都是稳定的，一些排序算法可能会改变具有相等键值的元素的相对顺序。因此，在选择排序算法时，需要根据具体的应用场景考虑排序算法的稳定性需求。

冒泡排序(Bubble Sort)

原理: 冒泡排序通过多次遍历数组，比较相邻元素的大小并交换位置，直到排序完毕。每一次遍历都会将最大的元素"冒泡"到末尾。
特点: 冒泡排序是一种比较简单的排序算法，实现起来容易理解，但效率较低。它的时间复杂度为O(n^2)，适用于小规模的数据排序。
适合解决的问题:冒泡排序适合用于排序较小规模的数据，而不适合处理大规模的数据。

快速排序(Quick Sort)

原理: 快速排序是基于分治法的思想。它首先选择一个基准元素(通常是数组中的某个元素)，然后将数组分割成两个子序列，其中一个子序列的元素都小于等于基准元素，另一个子序列的元素都大于等于基准元素。然后递归地对这两个子序列进行快速排序。
特点: 快速排序是一种基于比较的排序算法，它的平均时间复杂度为O(nlogn)。它具有原地排序和不稳定性的特点。
适合解决的问题:快速排序适用于大规模数据的排序，速度较快。它在实践中广泛应用于各种排序场景。

归并排序(Merge Sort)

原理: 归并排序也是基于分治法的思想。它将数组不断地分割成较小的子数组，然后将这些子数组逐个合并，直到排序完成。
特点: 归并排序的时间复杂度为O(nlogn)，具有稳定性和可靠性的特点。它需要额外的空间来存储临时的中间结果数组。
适合解决的问题:归并排序适用于大规模数据的排序，稳定性和可靠性使其适用于需要保持相同元素顺序的场景。

堆排序(Heap Sort)

原理: 堆排序基于完全二叉堆结构。它将待排序的数组构建成一个最大堆(或最小堆)，然后不断地从最大堆中取出堆顶元素并调整堆，直到所有元素有序。
特点: 堆排序的时间复杂度为O(nlogn)，它是一种原地排序算法，不需要额外的空间。但堆排序不是稳定的排序算法。
适合解决的问题: 堆排序适用于大规模数据的排序，特别适用于需要只保留部分最大(或最小)元素的场景。它在优先队列和求TopK问题中有广泛应用。

这些排序算法在实际应用中都有各自的应用场景和限制，选择正确的排序算法取决于数据规模、稳定性要求、空间复杂度要求和性能需求等因素。
冒泡排序由于性能很差，在实际工程中应用较少。
在对速度和空间复杂度有要求但对稳定性没要求的时候排序算法选用快速排序;
对稳定性有要求，但是对空间复杂度没有要求的时候排序算法选用归并排序;
在只需要保留最大/最小元素的应用场景下选用堆排序。