您的位置: 首页  >  文章  >  时空复杂度分析

时空复杂度分析

分类: 文章 • 2024-06-05 10:36:52

时空复杂度分析

数据结构和算法要解决的问题就是让代码运行得更快 , 让存储空间占得更少 , 所以时间和空间复杂度的分析是很重要的 .
那么究竟该如何分析 ?

大 O 复杂度表示法

我们经常会看到 O(1) O(n) O(logn) 这些时空复杂度的表示
其实这就是 大 O 复杂度表示法 , 它并不表示代码执行真正需要的时间 , 而是一种随着数据规模增长的趋势 , 其中 n 就是数据规模的大小 .

比如 n = 100 , 那么 O(n) 时间复杂度需要的时间可以假设为 100 s , 而 O(logn) 时间复杂度需要的时间就是 10 s , 差距一下就体现出来了 .
看下面这段代码

int cal(int n)
{
    int sum = 0;
    int i = 1;
    for (; i <= n; ++i)
    {
        sum = sum + i;
    }
    return sum;
}

功能是求 1 - n 的累加和, 假设执行一行代码的时间为一个 run_time

那么 3 4 两行代码执行用时为 2*run_time

而 5 7 两行代码都执行了 n 次, 所以需要的时间为 2n*run_time

于是整个代码运行的时间 T(n) = (2+2*n)*run_time

从这里我们可以看出, 整个代码运行的时间 T(n) 和每行代码运行的次数 n 成正比

设 f(n) = 2+2*n , 即每行代码运行次数的总和, 因为我们只是估算一个增长趋势, 而常数和系数不会对增长趋势产生什么影响, 所以可以简写为 f(n) = n

则有 T(n) = O(f(n)) , 即表示: 代码执行时间T(n)和代码执行次数f(n)成正比

则上面代码的时间复杂度可以表示为 O(n)

如何快速估算一段代码的时间复杂度?

1, 只关注循环执行次数最多的一段代码

2, 总的复杂度 = 复杂度量级最高的那段代码的复杂度

3, 嵌套代码的复杂度 = 嵌套内外代码复杂度的乘积

举几个例子说明一下:

int cal(int n)
{
    int sum_1 = 0;
    int p = 1;
    for (; p <= 100; ++p)
    {
        sum_1 = sum_1 + p;
    }

    int sum_2 = 0;
    int q = 1;
    for (; q <= n; ++q)
    {
        sum_2 = sum_2 + q;
    }

    int sum_3 = 0;
    int i = 1;
    int j = 1;
    for (; i <= n; ++i)
    {
        j = 1;
        for (; j <= n; ++j)
        {
            sum_3 = sum_3 +  i * j;
        }
    }

    return sum_1 + sum_2 + sum_3;
}

这段代码有三个循环

第一个循环固定执行 100 次

第二个循环执行 n 次

第三个双重循环执行 n*n 次

所以时间复杂度为 O(100 + n + n*n), 省略常数之后为 O(n + n*n)

但我们一般只关注最高阶, 即时间复杂度为 O(n^2)

再来看看下面这个代码

int f(int n)
{
    int sum = 0;
    int i = 1;
    for (; i < n; ++i)
    {
        sum = sum + i;
    }
    return sum;
}

int cal(int n)
{
    int ret = 0;
    int i = 1;
    for (; i < n; ++i)
    {
        ret = ret + f(i);
    }
}

在cal函数中, 第18行代码执行了n次, 但是它每次都调用了f(int)函数, 在f(int)函数中, 第7行代码要执行n次, 所以第7行代码一共执行了n*n次, 所以函数cal的时间复杂度是O(n^2)

其实在实际使用中, 时间复杂度的量级就那么几个, 按从小到大排有

常数级: O(1)

对数级: O(logn)

线性级: O(n)

线性对数级: O(nlogn)

平方级: O(n^2)

立方级: O(n^3) . . . O(n^k)

指数级: O(2^n)

阶乘级: O(n!)

对于这些时间复杂度量级, 可以分为两类:多项式量级和非多项式量级

其中非多项式量级只有: O(2^n)和O(n!)

我们把时间复杂度为非多项式量级的算法问题称为 NP(非确定多项式)问题, 当数据规模n越来越大时, 非多项式算法的执行时间会急剧增长, 因此时间复杂度为非多项式量级的算法是非常低效的!

对于O(1)时间复杂度, 只要执行时间不随n增大而增长, 都可以称为O(1)时间复杂度, 也就是说, 只要代码里没有循环和递归, 即使有成千上万行代码, 时间复杂度也是O(1)

对于O(logn)和O(nlogn), 这是很常见的时间复杂度量级, 同时也是最难分析的

i = 1;
while (i <= n)
{
    i = i * 2;
}

例如这个代码, i从1开始, 每次增长2倍, 即 2^0, 2^1, 2^2, 2^3 . . . 2^x = n

x即为第4行代码执行的次数, 可得 x = log2n, 所以这段代码时间复杂度为O(log2n)

我们把代码变一下

i = 1;
while (i <= n)
{
    i = i * 3;
}

可以得到时间复杂度为O(log3n)

其实, 无论底数为多少, 我们记做O(logn), 因为对数之间可以相互转换, 即

log3n = log32*log2n

其中 log32是常数, 可以省略.

还有一种表示时间复杂度O(m+n)

int cal(int m, int n)
{
    int sum_1 = 0;
    int i = 1;
    for (; i < m; ++i)
    {
        sum_1 = sum_1 + i;
    }

    int sum_2 = 0;
    int j = 1;
    for (; j < n; ++j)
    {
        sum_2 = sum_2 + j;
    }

    return sum_1 + sum_2;
}

因为我们无法预估m和n的大小, 所以时间复杂度记为O(m+n)

空间复杂度

相对于时间复杂度, 空间复杂度的分析就容易多了.

空间复杂度全称是渐进空间复杂度, 表示算法的存储空间和数据规模之间的增长关系

常用的空间复杂度量级有O(1), O(n), O(n^2)

void print(int n)
{
    int i = 0;
    int* a = new int[n];
    for (; i < n; ++i)
    {
        a[i] = i * i;
    }

    for (i = n - 1; i >= 0; --i)
    {
        std::cout << a[i] << "\n";
    }
}

在这个代码中, 我们申请了一个int型变量存储i, 它的大小是固定的, 不随n改变而改变;还申请了一个大小为n的int型数组, 它的大小随n的改变而改变, 所以这个代码的空间复杂度为O(n).

我们最常见的复杂度量级其实只有五种

O(1), O(logn), O(n), O(nlogn), O(n^2)

时空复杂度分析

相关推荐