时间复杂度¶

大O/大Θ 表示法¶

• 大O表示法（O）：表示算法的上界，描述算法在最坏情况下（时间上限）的时间复杂度。例如，O(n^2) 表示算法的时间复杂度不会超过 n^2 的某个常数倍。
• 大Θ表示法（Θ）：表示算法的紧确界，描述算法在平均情况下（时间上限和时间下限）的时间复杂度。例如，Θ(n log n) 表示算法的时间复杂度在 n log n 的某个常数倍范围内。

快速幂¶

快速幂是一种高效计算大整数幂的方法，时间复杂度为 O(log n)。其基本思想是利用指数的二进制表示，将幂运算分解为若干次平方和乘法运算。例如，要算2^10，它会先算2 * 2^9，再算 2 * 2 * 2^{8……。利用了倍增思想后，如果指数是偶数，可以算2}(n/2)然后把它平方一下（square）就行了；如果指数是奇数，就先算2^(n-1)，变回偶数情况处理。将时间复杂度从 O(n) 降低到 O(log n)。

有序列表的查找：从O(n^2)到O(n)¶

使用双指针可以将有序列表的查找时间复杂度从 O(n^2) 降低到 O(n)。例如，在2个有序数组中寻找两个数，使它们相等。传统的双重循环方法需要 O(n^2) 的时间复杂度（嵌套循环），而使用双指针方法可以在 O(n) 的时间内完成。具体做法是：一个指针从数组1的开始位置向右移动，另一个指针从数组2的开始位置向右移动，根据当前两个指针所指元素进行比较，调整指针的位置。