算法的时间复杂度和空间复杂度

用户11983512

发布于 2026-01-09 14:29:39

1640

文章被收录于专栏：用户11983512的专栏用户11983512的专栏

前言

又到了我们学习新知识的时候了(｡◕ˇ∀ˇ◕)，做题时我们经常遇到超时、程序崩溃、内存超限等问题，这让我们感到十分苦恼，而究竟怎么分析并解决它呢，今天就迎来了我们的第一个朋友——复杂度。

一、复杂度

衡量一个算法的优劣来根据复杂度来分析，它分为时间复杂度和空间复杂度，顾名思义也就是从时间和空间两个维度进行分析。而我们可能已经利用过它，比如在我们写斐波那契数列时，由于超时我们用数组来代替递归减少时间，如下，这就是用空间换时间的方法。

long long Fib(int N)
{
	if (N < 3)
		return 1;
	return Fib(N - 1) + Fib(N - 2);
}

long long Fib(int N)
{
    if (N == 0) 
        return 0;
    if (N == 1) 
        return 1;
    long long* arr = (long long*)malloc((N + 1) * sizeof(long long));
    arr[0] = 0;
    arr[1] = 1;
    for (int i = 2; i <= N; i++) 
    {
        arr[i] = arr[i - 1] + arr[i - 2];
    }
    long long result = arr[N];  
    free(arr); 
    return result;
}

二、时间复杂度

1、概念

在计算机科学中，算法的时间复杂度是一个函数，一般用F(N)表示，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但由于受到设备性能硬件不同，无法计算，所以才有了时间复杂度这个分析方式。

一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

2、引进大O的渐进表示法

求它的时间复杂度

#include <stdio.h>
#include <stdlib.h>  
int main() 
{
    int n;
    scanf("%d", &n);
    int count = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            count++;
        }
      
    }
    for (int i = 0; i < n; i++)
    {
        count++;
    }
   
    return 0;
}

由于上面定义我们很快就能求出来执行的操作次数为n2+n,则为F(N)=n2+n. 实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。

大O的渐进表示法 大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。 推导大O阶方法： 1、用常数1取代运行时间中的所有加法常数。 2、在修改后的运行次数函数中，只保留最高阶项(由于电脑CPU一秒可以运行大约2.667亿条指令，故n小时影响小，只看影响大的即最高项） 3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O 阶。 在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

故上面的时间复杂度为O(N)=N2。

3、常见时间复杂度

下面是不同复杂度随n执行次数的变化趋势

由此可看出来，不同时间复杂度一定程度上决定了算法的效率，下面会逐个讲解不同复杂度来帮助理解

4、常见时间复杂度举例

(1)常数阶O(1)

所谓常数阶，就是一个程序运行一个固定的次数（为常数次），那这个代码程序的时间复杂度就是O(1),其中1表示常数。如

#include <stdio.h>
#include <stdlib.h>  
int main() 
{
    int n = 5;
    int count = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            count++;
        }
      
    }
   
    return 0;
}

这个执行次数为5*5=25为常数，故它的时间复杂度就是O(n)。

(2)线性阶O(n)

线性阶嘛，是指算法的执行时间与输入规模 n 成正比例关系 —— 当输入规模 n 增大时，算法的执行次数（或耗时）会按相同比例增长。如

#include <stdio.h>
#include <stdlib.h>  
int main() 
{
    int n ;
    scanf("%d", &n);
    int count = 0;
    for (int i = 0; i < n; i++)
    {
       
            count++;
    }
    for (int i = 0; i < 5; i++)
    {
            count++;
    }
    return 0;
}

这个执行次数为n+5，由大O渐进法，5可忽略不计，故这类代码时间复杂度为O(n)。

(3)平方阶O(n2)

平方阶就如通把O(n)在嵌套一遍例如：

#include <stdio.h>
#include <stdlib.h>  
int main() 
{
    int n ;
    scanf("%d",&n);
    int count = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            count++;
        }
    }
    return 0;
}

它的时间复杂度就是O(n2) 了。

(4)对数阶O(logn)

对数阶（记为 O (log n)），就是是指算法的执行次数随输入规模 n 的增长呈对数级趋势—— 核心特点是 “每次操作都会将问题规模缩小固定比例（通常是减半）”，因此执行次数增长极慢。

注意在复杂度中logn为以2为底的对数的简写，不是我们平常以为的以10为底的

代码例如

#include <stdio.h>
int bi(int arr[], int n, int target)
{
    int left = 0;          
    int right = n - 1;    
    while (left <= right) 
    {
        int mid = left + (right - left) / 2;  
        if (arr[mid] == target) 
        {
            return mid;  
        }
        else if (arr[mid] < target) 
        {
            left = mid + 1;
        }
        else {
            right = mid - 1; 
        }
    }
    return -1; 
}

int main() 
{
    int arr[] = { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 };  
    int n = sizeof(arr) / sizeof(arr[0]); 
    int t;
    scanf("%d", &t);
    int index = bi(arr, n, t);
    if (index != -1) 
    {
        printf("目标元素 %d 在数组中的索引为：%d\n", t, index);
    }
    else
    {
        printf("未找到目标元素 %d\n", t);
    }

    return 0;
}

这是对数阶中常见的二分方法，一次缩小一半即2m=n,m=logn,即这类时间复杂度为O(logn)。

(5)nlogn阶O(nlogn)

这个也就相当于O(logn)的代码循环n次如

#include <stdio.h>
int bi(int arr[], int n, int target)
{
    int left = 0;          
    int right = n - 1;    
    while (left <= right) 
    {
        int mid = left + (right - left) / 2;  
        if (arr[mid] == target) 
        {
            return mid;  
        }
        else if (arr[mid] < target) 
        {
            left = mid + 1;
        }
        else {
            right = mid - 1; 
        }
    }
    return -1; 
}

int main() 
{
    int arr[] = { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 };  
    int n = sizeof(arr) / sizeof(arr[0]); 
    int y = n;
    while (y--)
    {
        int t;
        scanf("%d", &t);
        int index = bi(arr, n, t);
        if (index != -1)
        {
            printf("目标元素 %d 在数组中的索引为：%d\n", t, index);
        }
        else
        {
            printf("未找到目标元素 %d\n", t);
        }
    }
    return 0;
}

就把上面代码改一下就形成了时间复杂度为O(nlogn)的代码了，是不是比较好理解

(6)立方阶O(n3)

这类就是3个复杂度叠加,与n2类似，就不举例了

(6)指数阶O(2n)

时间复杂度的指数阶（通常记为 O (2ⁿ)、O (3ⁿ) 等），是指算法的执行次数随输入规模 n 的增长呈指数级趋势—— 核心特点是 “每增加一个输入单位，执行次数就会翻倍（或按固定倍数增长）”，因此增长速度极其迅猛如未优化的递归斐波那契数列计算

long long Fib(int n)
{
	if (n < 3)
		return 1;
	return Fib(n - 1) + Fib(n - 2);
}

下面是这个函数调用过程

呈二叉树形状，即调用次数为20+21+……+2n-2=2n-1-1,但实际比这小，呈现这个形状

但可忽略比记，由大O渐进法，时间复杂度为O(2n)

5、总结

时间复杂度是衡量算法执行效率的核心指标，不同阶的复杂度在性能表现上差异显著，选择适配的算法与数据结构能更高效地处理问题；若时间复杂度过高（如平方阶 O (n²)、指数阶 O (2ⁿ)），会造成严重性能损失，不利于大规模数据场景或实时系统的应用。所以利用高效类的时间复杂度来以提升程序效率、降低资源消耗是重要的

我们平常遇到的很多都是许多结构叠加，这时就要用大O的渐进表示法来判断时间复杂度。

三、空间复杂度

1、概念

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。注意：函数运行时所需要的栈空间在编译期间已经确定好了，因此

空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。但并不代表它不重要了，例如

在嵌入式开发中，设备内存资源有限，需严格控制空间复杂度以避免内存溢出；
在大数据处理场景，若算法空间复杂度为O(n)，当n达千万级时，内存消耗将成为性能瓶颈。

2、常见空间复杂度类型：

空间复杂度	说明	示例
O(1)	额外空间固定，不随输入规模n变化	两变量交换值（仅用临时变量）
O(n)	额外空间随n线性增长	用长度为n的数组存储斐波那契数列中间结果
O(log n)	额外空间随n对数增长	二分查找的递归调用栈（深度为log₂n）

3、常见空间复杂度类型举例

(1)O(1)

void cm(int *a,int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}时间复杂度

这里通过创建新的变量来交换a,b的值，创建一个临时变量，故空间复杂度为O(1)。

(2)O(n)

void cm(int n) 
{
    int* arr = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++)
     {
        arr[i] = i;
    }
    for (int i = 0; i < n; i++)
     {
        printf("%d ",arr[i]);
    }
    free(arr);
}

这段代码是通过创建一个元素个数为n的数组来实现目的，额外用的空间为n * sizeof(int)，其大小与输入规模n成正比，因此空间复杂度为 O(n)。

(3)O(logn)

int binarySearch(int arr[], int left, int right, int target)
{
    if (left > right) 
        return -1;  
    int mid = left + (right - left) / 2;
    if (arr[mid] == target)
        return mid;
    return (arr[mid] < target)? binarySearch(arr, mid + 1, right, target): binarySearch(arr, left, mid - 1, target);
}

还是我们的2分，这段代码的空间复杂度为O(log n)，分析如下：该代码是递归版二分查找，其空间消耗核心来自递归调用栈。每次递归调用会在栈中保存函数参数（arr、left、right、target）和局部变量（mid），形成一层栈帧。由于二分查找每次将问题规模减半（查找范围从n→n/2→n/4…），最多递归log₂n次，因此栈的深度为log₂n，额外空间随n的对数增长，最终空间复杂度为O(log n)。