[数据结构与算法]讲讲复杂度~

1.时间复杂度

1.1 时间复杂度的概念

算法的时间复杂度在计算机科学中，是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知
道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。不一定要知道具体的次数，只需要知道大概就可以。

看个例子：

void Fun(int n)
{
    int count = 0;
    int i = 0;
    for(i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            count++;
        }
    }

    for(i = 0; i < 2*n; i++)
    {
        count++;
    }

    int m = 10;
    for(i = 0; i < m; i++)
    {
        count++;
    }
}
        

当n为上述代码块中count++语句执行了几次呢？

Fun（n）= n^2 + n*2 + 10

• N= 10? ? ? ? ? ? ? ? F(N) = 130
• N = 100? ? ? ? ? ? ?F(N) = 10210
• N = 1000? ?????????F(N) = 1002010

?找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这
里我们使用大O的渐进表示法。

1.2 大O的渐进表示法

推到大O阶的方法：

1. 用常数1取代运行时间中的所有加法常数。
2. 在修改后的运行次数函数中，只保留最高阶项。
3. 如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

这时刚刚Fun函数的时间复杂度为O(n^2)。通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。

另外有些算法的时间复杂度存在最好、平均和最坏情况：
最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)
例如：在一个长度为N数组中搜索一个数据x
最好情况：1次找到
最坏情况：N次找到
平均情况：N/2次找到
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)。

1.3 常见时间复杂度的计算

1.

void Func3(int N, int M)
{
    int count = 0;
    for (int k = 0; k < M; ++ k)
    {
        ++count;
    }
    for (int k = 0; k < N ; ++ k)
    {
        ++count;
    }
    printf("%d\n", count)；
}
//对于该函数，M和N都是不确定的，所以时间复杂度应为O（N+M）
//假如说M远远大于N，那么可以忽略N，写为O（M）
//假如说N远远大于M，那么可以忽略N，写为O（N）
//如果差不多大那么要写为O（N+M）。

?2.

const char * strchr ( const char * str, int character )
{
    while(*str)
    {
        if(character == *str)
            return str;
        else
            str++;
    }
    return NULL;
}
//可以分析出这是一个从字符串中查找字符的函数
//对于这种函数要拿具体的字符串来分析，假如说查找的就是字符串的第一个字符
//那么就很简单了，运行1次，假如说找不到呢？或者说要找的字符在字符串末尾
//那么就要运行N次了，在这里只能取最坏的情况，所以时间复杂度应为O(N)

?3.

void BubbleSort(int* a, int n)
{
    assert(a);
    for (size_t end = n; end > 0; --end)
    {
        int exchange = 0;
        for (size_t i = 1; i < end; ++i)
        {
            if (a[i-1] > a[i])
            {
                Swap(&a[i-1], &a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0)
            break;
    }
}
//计算冒泡函数的时间复杂度也要根据实际的数字排列计算
//在这里也是有最坏和最好的两种情况：
//最好的就是给的数字序列就是一组从小到大的数组
//最坏的就是给的数字序列是一组从大到小的数组，需要从头到尾全部换一遍
//取最坏的情况计算时间复杂度

?4.

// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{
    assert(a);
    int begin = 0;
    int end = n-1;
    while (begin < end)
    {
        int mid = begin + ((end-begin)>>1);
        if (a[mid] < x)
            begin = mid+1;
        else if (a[mid] > x)
            end = mid;
        else
            return mid;
    }
    return -1
}
//二分查找也分为两种情况：
//最好的情况，第一次就找到了那么就是O(1)
//最坏的情况就是一直找到最后，最后的区间只有要找的数字
//假设我们找了x次
//1*2*2....*2=2^x =N（用折纸法大概估算一下量级），一共找了log 2 N次
//所以时间复杂度应取情况最差时O(log 2 N)

?补充：有时候会把O(log 2 N)简写成O(log N),因为在计算机上写底数不方便，也有的资料写O(lgN)。其他的一般都不简写。

?5.

// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
    if(0 == N)
        return 1;
    return Fac(N-1)*N;
}
//分析代码，发现是复杂度为递归的次数
//所以时间复杂度为O（N）。但不能一味地只看递归次数。

long long Fac(size_t N)
{
    if(0 == N)
        return 1;
    int i = N;
    while(i--)
        printf("%d",i);
    return Fac(N-1)*N;
}
//对于这个函数，就应该是求等差数列之和了。
//时间复杂度为O(N*N)
//所以求时间复杂度时，一定要分析代码

递归算法时间复杂度计算：

1. 每次函数调用的是O(1)，那么就看递归次数；
2. 每次函数调用不是O(1)，那么就看它递归调用中次数的累加。（类似等差数列求和）

6.?

// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{
    if(N < 3)
        return 1;
    return Fib(N-1) + Fib(N-2);
}
//该题时间复杂度是O(2^N)

?可以将其看为是一个三角形：

所以根据等比数列求和公式可以得出和为 2^(N-1) - 1。则时间复杂度为O(N*N)。

?2.空间复杂度

2.1空间复杂度的概念

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度 。
空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。
注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
?

2.2空间复杂度的计算

1.

// 计算BubbleSort的空间复杂度？
void BubbleSort(int* a, int n)
{
    assert(a);
    for (size_t end = n; end > 0; --end)
    {
        int exchange = 0;
        for (size_t i = 1; i < end; ++i)
        {
            if (a[i-1] > a[i])
            {
                Swap(&a[i-1], &a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0)
            break;
    }
}
//空间复杂度计算的是程序运行过程中，除需要的空间外额外开辟的空间。
//不要将n也算进去。
//在这里只需要将end、exchange、i算出来就行
//也不要认为为exchange开辟的空间是随N变化的，因为exchange只开辟一个空间
//原因是这样的：
//在一次循环进去后是开辟exchange的，但由于exchange是局部变量，所以这次循环过后
//他便释放这个空间，下次进入循环再为exchange开辟一个空间。
//所以空间复杂度为O（1）

2.?

// 计算Fibonacci的空间复杂度？
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{
    if(n==0)
        return NULL;
    long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));
    fibArray[0] = 0;
    fibArray[1] = 1;
    for (int i = 2; i <= n ; ++i)
    {
        fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
    }
    return fibArray;
}
//首先初始化了一个指针，而后动态开辟了n+1个，最后又开辟一个i，所以这就是n+3个。
//可以知道其应该为O(N)。

3.?

// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{
    if(N == 0)
        return 1;
    return Fac(N-1)*N;
}
//空间复杂度为O(N)

?4.

// 计算斐波那契递归Fib的空间复杂度？
long long Fib(size_t N)
{
    if(N < 3)
        return 1;
    return Fib(N-1) + Fib(N-2);
}
//这个题要与函数栈帧相联系，要清楚，空间是可以重复利用的
//答案为O(N)

?递归函数栈帧的创建：

?函数的调用是一级一级的，这时函数栈帧为N-1个，而后2销毁，调用1：

?调用完1后销毁，走到3，销毁三，调用4，这样循环下去，每次的栈帧都是用的上次销毁完的空间：

?所以只开辟了N个空间，那么空间复杂度也就为O(N).。

3.常见复杂度对比