【数据结构】时间复杂度和空间复杂度分析

文章目录

研究时间复杂度的重要性

我们知道CPU提升的速度是很慢的,就算夸张点10年间提升了10000倍
如果一个可以有时间复杂度为 O(n)O(n)O(n) 的算法的程序,我们写成了 O(n2)O(n^2)O(n2),那么程序只提升了 10000=100\sqrt {10000}=10010000​=100倍 ,而对于O(n)O(n)O(n)时间复杂度的算法却能提升10000倍

最坏情况和平均情况

示例:
在一个由n个元素的数组中,按顺序查找一个数
最好的情况是查找的就是第一个数,复杂度 O(1)O(1)O(1)

平均运行时间需要从概率来看,也就是期望
每个数是查找的概率是 1/n1/n1/n ,然后乘以对应的随机变量
期望 E=11/n+21/n+...+n1/n=(1+n)/2E = 1 * 1/n + 2 * 1/n + ... + n * 1/n = (1 + n) / 2E=1∗1/n+2∗1/n+...+n∗1/n=(1+n)/2
所以平均查找次数是(1+n)2\frac {(1 + n)} { 2}2(1+n)​次

最坏情况是这个数字在最后一个位置,所以需要查找n次


平均运行时间是最有意义的,因为这是一个通常的运行时间,比如除了双十一外的364天,淘宝运行时间都是1秒,但是最坏情况是双十一那天,淘宝运行时间可能是100秒

最坏情况运行时间是一种保证,也就是说运行时间不会再多了,这在实际应用中是一个很重要的需求,所以一般我们说的时间复杂度都是指最坏情况的运行时间

时间复杂度的渐进表示法

我们把语句的总的执行次数记作 T(n)T(n)T(n)
T(n)T(n)T(n)是关于问题规模n的函数
大O表示法

  • T(n)=O(f(n))T(n) = O(f(n))T(n)=O(f(n))表示存在常数C>0,n0>0C>0,n_0>0C>0,n0​>0,使得当n>=n0n>=n_0n>=n0​时有 T(n)<=Cf(n)T(n) <= Cf(n)T(n)<=Cf(n)

对于充分大的nnn而言,f(n)f(n)f(n)是T(n)T(n)T(n)的某种上界
但是一个东西的上界可以有很多个,太大的上界对我们分析算法复杂度没有什么参考意义,我们希望跟真实情况越贴近越好

推导大O阶:

  1. 用常数取代运行时间中的所有加数常数
  2. 在修改后的运行次数函数中,只保留最高阶项
  3. 如果最高阶项且不是1,则去除与这个项相乘的常数 得到的结果就是大O阶

例1:T(n)=4n3T(n) = 4n^{3}T(n)=4n3 + 7n27n^{2}7n2 + 53logn53logn53logn + 222
推导大O阶得:T(n)=O(n3)T(n) = O(n^3)T(n)=O(n3)

例2:O(3)=O(1)O(3) = O(1)O(3)=O(1)

例3: O(2logn+n/2)=O(n)O(2logn + n/2) = O(n)O(2logn+n/2)=O(n)


  • T(n)=Ω(g(n))T(n) = \Omega(g(n))T(n)=Ω(g(n))表示存在常数C>0,n0>0C>0,n_0>0C>0,n0​>0,使得当n>=n0n>=n_0n>=n0​时有 T(n)>=Cg(n)T(n) >= Cg(n)T(n)>=Cg(n)
  • T(n)=θ(h(n))T(n) = \theta(h(n))T(n)=θ(h(n))表示同时有 T(n)=O(h(n))T(n) = O(h(n))T(n)=O(h(n))和 T(n)=Ω(h(n))T(n) = \Omega(h(n))T(n)=Ω(h(n))

常见的时间复杂度

常见的时间复杂度所耗时间的大小排名:
O(1)<O(logn)<O(n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)O(1)<O(logn)<O(n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)O(1)<O(logn)<O(n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)学数学的时候用的记忆技巧:对幂指阶超

空间复杂度分析

算法空间复杂度的计算公式记作: S(n)=O(f(n))S(n) = O(f(n))S(n)=O(f(n)) ,其中 nnn 为问题的规模, f(n)f(n)f(n)为语句关于 nnn 所占存储空间的函数

一个程序执行时,除了需要存储程序本身的指令、常数、遍历和输入数据外,还要存储对数据操作的存储单元

如果输入数据所占空间只取决于问题本身,与算法无关,那我们只需要分析该算法在实现时所需的辅助空间,也就是分析额外使用的空间即可


例如:
下面的代码输入数据matrix所占空间与算法优劣没有关系,所以我们只需要看额外的使用空间即可

这里我们定义了变量:nmdxyabn、m、d、x、y、a、bn、m、d、x、y、a、b,数组:dxdyresdx,dy,resdx,dy,res
用大O推导法知S(N)=O(N)S(N) = O(N)S(N)=O(N),其中NNN表示矩阵中的所有元素个数N=nmN=n*mN=n∗m(需要resresres数组来存储信息

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        if(!matrix.size() || !matrix[0].size()) return {};
        int n = matrix.size(), m = matrix[0].size();
        vector <int> res;
        
        int dx[] = {0, 1, 1, -1}, dy[] = {1, -1, 0, 1};

        int x = 0, y = 0, d = 0;
        for (int i = 1; i <= n * m; i ++) {
            res.push_back(matrix[x][y]);
            matrix[x][y] = INT_MAX;

            if (i == n * m) break;
            // 利用(a,b)找到下一个可以走的点
            int a = x + dx[d], b = y + dy[d];
            while(a < 0 || a >= n || b < 0 || b >= m || matrix[a][b] == INT_MAX) {
                d = (d + 1) % 4;
                a = x + dx[d], b = y + dy[d];
            }

            // 让(x,y)变成下一个可走的点,然后进入下一个循环
            x = x + dx[d];
            y = y + dy[d];
            if (d == 0 || d == 2) d = (d + 1) % 4;
        }

        return res;
    }
};
【数据结构】时间复杂度和空间复杂度分析【数据结构】时间复杂度和空间复杂度分析 meteorsh 发布了260 篇原创文章 · 获赞 95 · 访问量 10万+ 私信 关注
上一篇:2019-08-10 纪中NOIP模拟赛B组


下一篇:Educational Codeforces Round 88 (Rated for Div. 2) 现ABCE 补D 欠F