这学期开设的《数据结构与算法》课程内容都快过半了,这里挖个坑总结一下在算法复杂度方面的一些内容。

一些标记法

大 $O$ 标记法:若存在常数$k,n_0$,使得算法在解决问题规模$n$在$n \ge n_0$时,其需要的步骤数小于等于$k\times f(n)$,则称算法的时间复杂度可由$O(f(n))$表示。

小 $o$ 标记法:上述表述中“小于等于”换为“小于”。

大$\Omega$标记法:上述表示中“小于等于”换为“大于等于”。

大$\omega$标记法:上述表述中“小于等于”换为”大于”。

$\Theta$标记法:上述表述中“小于等于” 换为“等于”, 即其复杂度与$f(n)$同阶。

专业术语

大$O$:渐进上界;大$\Omega$:渐进下界;大$\Theta$:渐进精确界。

算法分析中常用级数

算数级数

$$ T(n) = 1+2+3+\cdots+n = n(n+1) = O(n^2) $$

幂方级数

$$ \begin{array}{l}{T_{2}(n)=1^{2}+2^{2}+3^{2}+\ldots+n^{2}=n(n+1)(2 n+1) / 6=O\left(n^{3}\right)} \\ {T_{3}(n)=1^{3}+2^{3}+3^{3}+\ldots+n^{3}=n^{2}(n+1)^{2} / 4=O\left(n^{4}\right)} \\ {T_{4}(n)=1^{4}+2^{4}+3^{4}+\ldots+n^{4}=n(n+1)(2 n+1)\left(3 n^{2}+3 n-1\right) / 30=O\left(n^{5}\right)} \\ {\cdots} \\ {\sum_{k=0}^{n} k^{d} \approx \int_{0}^{n} x^{d+1} d x=\left.\frac{1}{d+1} x^{d+1}\right|_{0} ^{n}=\frac{1}{d+1} n^{d+1}=O\left(n^{d+1}\right)}\end{array} $$

几何级数

$$ \begin{array}{l}{\left.T_{a}(n)=a^{0}+a^{1}+a^{2}+\ldots+a^{n}=\left(a^{n+1}-1\right) /(a-1)\right)=O\left(a^{n}\right)} \\ {1+2+4+\ldots+2^{n}=2^{n+1}-1=O\left(2^{n+1}\right)=O\left(2^{n}\right)}\end{array} $$

收敛级数

$$ \begin{array}{l}{1 / 1 / 2+1 / 2 / 3+1 / 3 / 4+\ldots+1 /(n-1) / n=1-1 / n=O(1)} \\ {1+1 / 2^{2}+\ldots+1 / n^{2}<1+1 / 2^{2}+\ldots=\pi^{2} / 6=O(1)} \\ {1 / 3+1 / 7+1 / 8+1 / 15+1 / 24+1 / 26+1 / 31+1 / 35+\ldots=1=O(1)}\end{array} $$

主方法定理(Master Theorem)

刚开始接触复杂度时我们应该遇到的主要是靠数for循环的层数之类的简单问题,但一些递归问题就有点棘手了,比如说Leetcode《414.第三大的数》就比较烦,显然用下面这种憨批写法很快也符合复杂度要求,但要是找第K大的数就无能为力了:

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        long first = LONG_MIN, second = LONG_MIN, third = LONG_MIN;
        for (int num : nums) {
            if (num > first) {
                third = second;
                second = first;
                first = num;
            } else if (num > second && num < first) {
                third = second;
                second = num;
            } else if (num > third && num < second) {
                third = num;
            }
        }
        return (third == LONG_MIN || third == second) ? first : third;
    }
};

查阅资料之后发现有一种基于快排的找n个数中第K大数字的算法。
Tips: 本题要求重复元素不占用次序号,即元素可以并列且若所求第k大元素不唯一只需返回最大元素,所以下面介绍的方法需要略加去重逻辑的修改。

int findKthmax(vector<int>& nums, int k, int start, int end){
        int left = start;
        int right = end;
        int pivot = nums[left];
        while(left<right){
            while(left<right && nums[right]<pivot) right--;
            nums[left] = nums[right];
            while(left<right && nums[left]>pivot) left++;
            nums[right] = nums[left];
        }
        nums[right] = pivot;
        if(right==k-1) return pivot;
        else if(right>k-1) return findKthmax(nums, k, start, right-1);
        else return findKthmax(nums, k, right+1, end);
}

思路自然也很简单,快排一次之后pivot就将数组分为两个部分,将pivot下标与k作比较即可知道第k大元素在哪半边,平均复杂度的迭代式并不难写:

$$ T(n) = T(\frac{n}{2})+O(n) $$

但这个式子要如何用Big-O Notation表示呢?这里就要引入主方法定理了:
对形$T(n)=aT(\frac{n}{b})+f(n)$的递推式,其中,n为问题规模,a为递推的子问题数量,n/b为每个子问题的规模(假设每个子问题的规模基本一样),f(n)为递推以外进行的计算工作。
分为以下三种情况:
屏幕快照 2019-10-04 下午11.29.46.png
显然,对我们的式子来说,$a = 1, b = 2, f(n) = O(n)$,符合情形三,$T(n) = \Omega(n)$,符合算法要求。

Last modification:July 29th, 2020 at 07:15 pm
If you think my article is useful to you, please feel free to appreciate