数据结构与算法|【落羽的落羽数据结构篇】算法复杂度

在这里插入图片描述

文章目录

一、数据结构和算法简介
二、算法复杂度
- 1. 时间复杂度
- 2. 空间复杂度

一、数据结构和算法简介

数据结构是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。没有一种单一的数据结构对所有用途都有用，所以我们要学习各种各样的数据结构，比如线性表、树、图、哈希等等。

算法，是定义良好的计算过程。简单来说，算法就是一系列的计算步骤，用来将输入数据转换成输出结果。衡量一个算法的好坏，需要从算法的复杂度来分析。

二、算法复杂度

算法在编写成可执行程序后，运行时需要耗费时间资源和空间（内存）资源，因此衡量一个算法的好坏，一般是从时间和空间两个维度来看，即时间复杂度和空间复杂度。时间复杂度主要衡量一个算法的运行快慢，空间复杂度主要衡量一个算法运行所需要的额外空间。

1. 时间复杂度

在计算机科学中，T(N)描述了该算法的指令执行次数，并不是计算程序的运行时间。因为一个程序的运行时间不仅关乎算法本身，还有编译器版本、机器配置新旧等等因素。
T(N)计算了程序的执行次数，假设每句指令执行时间基本一样（实际有差别但是微乎其微），那么执行次数和运行时间就成等比关系，执行次数就能代表程序运行时间效率的优劣。比如对于同一个问题，算法a的T(N)=N，算法b的T(N)=N²，那么算法a的时间效率优于算法b。

计算时间复杂度要注意：由于CPU一秒可以处理上亿条代码指令，所以变量的单次定义语句可以忽略，时间复杂度只计算循环语句。而我们计算时间复杂度只是想比较算法程序的增长量级，也就是N不断变大时T(N)的差别，而**常数项和低阶项对结果的影响很小，甚至最高项的系数也可以忽略影响，所以我们只保留最高项，并且它的系数视作1。如果T(N)中没有任何关于N的项，时间复杂度就是1。复杂度的最终表示通常使用O的渐进表示法。**
例如：
T(N)=3N²+2N+10，则时间复杂度为O(N²)
T(N)=5N³+N²+5N，则时间复杂度为O(N³)
T(N)=6，则时间复杂度为O(1)

来几个例子分析就懂了：

void Func1(int N) 
{ 
    int count = 0;   //忽略
    for (int i = 0; i < N ; ++i) 
    { 
        for (int j = 0; j < N ; ++j) 
        { 
            ++count; //N^2次
        } 
    } 
    for(int k = 0; k < 2*N ; ++k) 
    { 
        ++count; //2N次
    } 
    int M = 10; //忽略
    while(M--) 
    { 
        ++count; //10次
    }
}
//T(N)=N^2+2N+10  时间复杂度为O(N^2)

void Func2(int N)
{
    int count = 0;
    for(int k=0; k<100; k++)
    {
        ++count;    //100次
    } 
    printf("%d",count);
}
//T(N)=100  时间复杂度为O(1)

void func3(int n)
{
    int cnt = 1;
    while(cnt < n)
        cnt *= 2;
}
//n=2时，执行次数为1。n=4时，执行次数为2。n=16时，执行次数为4 ......
//假设执行次数为x，则2^x=n。x=log n，时间复杂度为O(logN)
//（对数的底数对结果的影响也可以忽略，因此不管底数是多少都可以省略不写，都表示为log n）

long long func4(size_t N)
{
    if(N==0)
        return 1;
    return func4(N-1)*N;
}
//递归也是一种循环，递归算法的时间复杂度是单次递归的时间复杂度乘递归次数
//时间复杂度为O(1)×N = O(N)

void func5(int N, int M)
{
    int count = 0;
    for(int k = 0; k<N; k++)
        count++;    //N次
    for(int k = 0; k<M; k++)
        count++;    //M次
    printf("%d", count);
}
//T(N)=N+M
//若N=M，则时间复杂度为O(N)。若M远大于N，则为O(M)。若N远大于M，则为O(N)

除此之外，有些算法的时间复杂度还存在最好、平均、最坏情况。最好情况是任意输入规模的最小运行次数（下界），最坏情况是任意输入规模的最大运行次数（上界）。一般情况下，我们都关注算法的最坏运行情况。比如冒泡排序算法，就存在这样的情况：
最好情况是数组已经有序，时间复杂度就是O(N)；最坏情况是数组完全逆序，时间复杂度是O(N²)，因此冒泡排序的时间复杂度取最差情况O(N²)
在这里插入图片描述

2. 空间复杂度

空间复杂度也是一个数学表达式，是对一个算法在运行过程中需要额外临时开辟的空间。空间复杂度并不是程序运行所占用的内存大小，计算的是变量的个数。大多数算法使用的是有限个变量，所以空间复杂度为O(1)。但对于递归算法，递归的空间复杂度等于单词递归的空间复杂度乘以递归次数，即O(1)×N=O(N)
在实际算法题目中，我们尤其关注时间复杂度，空间复杂度就不是特别重要了。