1.2 算法分析

级数

• 算数级数，与末项平方同阶
  T(n) = 1+2+...+n = n(n+1)/2 = O(n²)
• 幂方级数，比幂次高一阶
  T₂(n) = 1²+2²+...+n² = n(n+1)(2n+1)/6 = O(n³)
  T₃(n) = 1³+2³+...+n³ = n²(n+1)²/4 = O(n⁴)
  T₄(n) = 1⁴+2⁴+...+n⁴ = n(n+1)(2n+1)(3n²+3n-1)/30 = O(n⁵)
  幂方级数
• 几何级数，与末项同阶
  T_a(n) = a⁰+a¹+...+aⁿ = (aⁿ⁺¹-1)/(a-1) = O(aⁿ)
  1+2+4+...+2ⁿ = 2ⁿ⁺¹-1 = O(2ⁿ⁺¹) = O(2ⁿ)
• 收敛级数
  1/(1×2)+1/(2×3)+1/(3×4)+...+1/((n-1)×n) = 1-1/n = O(1)
• 几何分布
  (1-p)(1+2p+3p²+...+np^n-1+...) = 1/(1-p) = O(1), 0 < p < 1
• 调和级数
  1+1/2+1/3+...+1/n = Θ(logn)
• 对数级数
  log1+log2+log3+...+logn = log(n!) = Θ(nlogn)

循环与级数

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        O(1) Operation(i, j)

for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++)
        O(1) Operation(i, j)

for (int i = 1; i < n; i <<= 1)
    for (int j = 0; j < i; j++)
        O(1) Operation(i, j)

for (int i = 0; i <= n; i++)
    for (int j = 1; j < i; j += j)
        O(1) Operation(i, j)

取非极端元素
问题：给定整数子集S，|S| ≥ 3，取元素a ∈ S，要求a ≠ max(S) 且 a ≠ min(S)
算法：从S中任意取3个元素，因S为集合，元素互异，确定并排除最大值与最小值，余下元素即为结果。T(n) = O(1)

冒泡排序
问题：给定n个整数，按（非降）序排列
观察：有序序列中，任意相邻元素顺序；无序序列中，总有相邻元素逆序。
扫描交换：依次比较每对相邻元素，若逆序，则交换；若整个扫描过程中未发生交换，则排序完成，否则重复该过程。

void bubbleSort(int arr[], int n) {
    for (bool sorted = false; sorted = !sorted; n--) {
        for (int i = 1; i < n; i++) {
            if (arr[i - 1] > arr[i]) {
                swap(arr[i - 1], arr[i]);
                sorted = false;
            }
        }
    }
}

不变性：经k次扫描交换后，最大的k个元素必然就位
单调性：经k次扫描交换后，问题规模缩减至n - k
正确性：经至多n次扫描后，算法必然终止，且可获得正确结果
T(n) = O(n²)