时间复杂度和空间复杂度

2024-01-20 11:33:40

文章目录

时间复杂度
空间复杂度

时间复杂度

什么是时间复杂度？

n表示的是问题的规模，时间复杂度O(n)是：随着问题规模增长，时间增长的某种函数关系
这种以O( )来表示时间复杂度的方法，称为大O计法。
注意！计算时间复杂度不是看程序最少运行多少次，而是看最多运行多少次！

如何分析一段代码的时间复杂度？

（1）常数阶 O(1)

O(1)的特点就是如果一个算法执行次数是恒定的，不会因为n的变大而变大，那么就是O(1)。

举个例子

下面这个程序就和传入的n没有关系，因为不管n传多少，程序运行的步骤是固定的。

public static int solution(int n){
    int sum =0;
    sum = (1+n)*100/2;
    return sum;
}

注意没有O(2)，O(20)…常数都算为O(1)

（2）线性阶 O(n)

O(n)的话，陈旭执行次数会随着n的增长而线性增长

举个例子

最常见的就是循环

public static void solution(int n){
    for (int i = 0; i < n; i++) {
        System.out.println(i);
    }
}

（3）对数阶 O(logn)

对数阶按照直白的话来说就是，与O(n)每次离终点接近1相比，O(logn)每次会对剩下的举例进行切分，并更快速的接近终点
举个例子
下面这个每次循环后i = i*2；不断地加快i的前进速度

public static void solution(int n){
    for (int i = 0; i < n; i=i*2) {
        System.out.println(i);
    }
}

（4）O(max(m,n))，O(m+n)，O(m*n) 的区别

O(max(m,n))，O(m+n) 这两种其实就是线性的O(n)，O(m*n) 其实是O(n²)。
另外：O(max(m,n))，O(m+n) 常用在双链表合并之类的题目…如Leetcode #2 两数相加

（5）其他的阶

其实还有些
像是O(n²) ，就是两个O(n)嵌套，O(nlogn)同理
大概用到的就是以下的这些，将其排序得到：

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

空间复杂度

空间复杂度：即程序中开辟内存空间(创建变量or数据结构) 与程序规模n 的函数关系

首先注意，承载返回结果的数据结构是不算进空间复杂度的
空间复杂度只是针对起辅助作用的数据结构。。
什么意思？？举个例子
下面这段代码的空间复杂度不是O(n)而是O(1)，因为list是返回结果的承载数据结构，是不针对其进行考虑的，只用考虑创建的int i变量所以是O(1)…

public static List<Integer> solution(int n){
    ArrayList<Integer> list = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        list.add(i);
    }
    return list;
}

如果下面这种，在程序中只是辅助作用，但不进行返回的，那么就计算空间复杂度为O(n)

public static int solution(int n){
    int[] ints = new int[n];
    System.out.println(ints.length);
    for (int i = 0; i < n; i++) {
        ints[i] = i;          
    }
    int sum = 0;
    for (int anInt : ints) {
        sum+=anInt;
    }
    return sum;
}

如果只是在方法中创建了几个变量，创建变量的个数和输入的参数无关，那么就是O(1)
算法中定义了一个线性集合，如一个列表，并且集合大小和输入规模n成正比，空间复杂度记为O(n)
算法中定义了一个二维列表集合，并且集合的长和宽都和输入规模n成正比，空间复杂度记为O(n²)或者O（n*m)
递归过程就是一个进栈和出栈的过程，当进入一个新函数时，进行入栈操作，把调用的函数和参数信息压入栈中；当函数返回时，执行出栈。
递归的空间复杂度也是线性的，如果递归的深度是n，那么空间复杂度就是O(n)。

————— END —————

码农公寓