算法刻意练习之时间/空间复杂度

系统管理员 2022-12-02 04:25 240阅读 0赞

## 1 时间复杂度：是指执行当前算法所消耗的时间 ##

1、常数阶O(1)：无论代码执行了多少行，只要是没有循环等复杂结构，消耗的时间并不随着某个变量的增长而增长，那时间复杂度就都是O(1)
    例：
    int i = 1;
    j = 2;
    ++i;
    j++;
    int m = i + j;
    
    2、线性阶O(n)：大多数遍历
    例：for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化
    for(i=1; i<=n; ++i) {
       j = i;
       j++;
    }
    
    3、平方阶O(n²)：双重循环
    
    4、立方阶O(n³)：三重循环
    
    5、对数阶O(logN)：二分查找、二叉搜索树
    例：
    // 假设循环x次之后，i就小于等于1了，此时这个循环就退出了，也就是说n的1/2的x次方等于1，n*(1/2)^x = 1 --> n/2^x = 1 --> n = 2^x (2^x = n)  --> x = log2^n
    for (i = n; i >= 1; i = i / 2) {
        printf("%d", i);
    }
    // 假设循环x次之后，i就大于n了，此时这个循环就退出了，也就是说2的x次方等于n，2^x = n --> x = log2^n
    for (i = 1; i < n; i = i * 2) {
        printf("%d", i);
    }
    // 次数      i     n = 1024+
       1     |   2
       2     |   4
       3     |   8
       4     |   16
       5     |   32
       6     |   64
       7     |   128
       8     |   256
       9     |   512
       10    |   1024
    
    6、线性对数阶O(nlogN)：时间复杂度为O(logn)的代码循环n遍
    
    7、指数阶(2^n)：遍历满二叉树、递归
    
    8、O(n!): Factorial阶乘

## 2 空间复杂度：是指执行当前算法临时需要占用多少内存空间大小 ##

1、常量级空间：0(1)
    例：
    int i = 1;
    int j = 2;
    ++i;
    j++;
    int m = i + j;
    
    2、数组的长度：O(n)/O(N^2)。例：new Int[n+1] --> O(n)
    例：第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可
    int[] m = new int[n]
    for(i=1; i<=n; ++i) {
       j = i;
       j++;
    }
    
    3、递归的深度：O(n)。例：n = 5, 满二叉树有5层，递归满二叉树5次

## 3 时间空间复杂度汇总 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/6720297af8984372bb6454381180bb2c.png