第2天：常见的时间复杂度
内容提要
时间复杂度是算法运行时间随输入规模增加而增加的度量，常见的时间复杂度有O(1)、O(log n)、O(n)、O(n log n)、O(n²)和O(2ⁿ)。空间复杂度是算法运行时使用的内存量。排序算法如冒泡排序、选择排序和插入排序的时间复杂度为O(n²)，不适用于大规模输入。
延伸解读
时间复杂度与空间复杂度的权衡
文章指出，时间复杂度和空间复杂度分别关注运行时间和内存使用。例如，归并排序的时间复杂度为O(n log n)，但需要O(n)的辅助空间来合并子数组。而冒泡、选择、插入排序虽然时间复杂度为O(n²)，但空间复杂度为O(1)，属于原地排序。在实际开发中，需要根据场景权衡：内存充足时可选时间更优的算法，内存受限时则可能选择原地算法。
常见排序算法的效率对比
文章分析了冒泡、选择和插入排序，它们的时间复杂度均为O(n²)，且空间复杂度为O(1)。这些算法由于嵌套循环，在大规模输入下效率较低。相比之下，归并排序和快速排序的时间复杂度为O(n log n)，更适合处理大规模数据。因此，对于大数据集，应优先选择O(n log n)的排序算法，而O(n²)算法仅适用于小规模数据或教学演示。
指数复杂度算法的适用场景
文章以汉诺塔问题为例，说明O(2ⁿ)指数时间复杂度算法的运行时间随输入规模翻倍增长，即使输入稍大也会变得不可行。因此，这类算法仅适用于输入规模很小的情况，例如n≤20。在实际应用中，应避免使用指数复杂度算法处理大规模数据，或考虑用动态规划等优化手段降低复杂度。
Q&A
什么是时间复杂度？
时间复杂度是算法运行时间随输入规模增加而增加的度量。
常见的时间复杂度有哪些？
常见的时间复杂度有O(1)、O(log n)、O(n)、O(n log n)、O(n²)和O(2ⁿ)。
O(n²)时间复杂度的算法有哪些？
冒泡排序、选择排序和插入排序的时间复杂度为O(n²)。
O(1)和O(n)的时间复杂度有什么区别？
O(1)表示常数时间复杂度，执行时间与输入规模无关；O(n)表示线性时间复杂度，运行时间与输入规模成正比。
什么是空间复杂度？
空间复杂度是算法运行时使用的内存量，包括辅助空间和输入空间。
时间复杂度和空间复杂度的主要区别是什么？
时间复杂度关注算法的运行时间，而空间复杂度关注算法的内存使用。
