1.2 算法分析

2020-06-11 本文已影响0人月影追猎者

级数

算数级数，与末项平方同阶
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)

${\textstyle \sum_{i=0}^{n-1}} n = n + n + ... + n = n^{2} = O\left ( n^{2} \right )$

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

${\textstyle \sum_{i=0}^{n-1}} i = 0 + 1 + 2 + ... + \left ( n - 1 \right ) = \frac{n\left ( n - 1 \right ) }{2} = O\left ( n^{2} \right )$

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

$1 + 2 + 4 + ... + 2^{\log_{2}{(n-1)} } = {\textstyle \sum_{k=0}^{\left \lfloor \log_{2}{\left ( n - 1 \right ) } \right \rfloor }} 2^{k} = 2^{\left \lceil \log_{2}{n} \right \rceil } - 1 = O\left ( n \right )$

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

${\textstyle \sum_{k=0}^{n}} \left \lceil \log_{2}{i} \right \rceil = O\left ( nlogn \right )$

取非极端元素
问题：给定整数子集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²)

1.2 算法分析

猜你喜欢

热点阅读