DS：时间复杂度和空间复杂度

欢迎各位来到 Harper.Lee 的学习世界！

博主主页传送门：Harper.Lee的博客主页

想要一起进步的uu欢迎来后台找我哦！

        本片博客主要介绍的是数据结构中关于算法的时间复杂度和空间复杂度的概念。

一、算法

1.1 什么是算法？

         算法(Algorithm):就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。

1.2 算法的复杂度

        算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
        时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度，计算机的配置变得越来越高，对内存（空间复杂度）的关注也就没那么高了。所以我们如今已经不需要再特别关注一个算法的空间复杂度。目前计算机行业的硬件方面已经遇到瓶颈期了。

摩尔定律：其核心内容是当价格不变时，集成电路上可容纳的晶体管数目约每隔18个月至24个月便会增加一倍，同时性能也将提升一倍。换言之，每一美元所能买到的电脑性能，将每隔18个月翻两倍以上。这一定律揭示了信息技术进步的速度，为半导体行业的发展提供了长期的发展目标和预测。

二、时间复杂度

2.1 时间复杂度的概念

        在计算机科学中，算法的时间复杂度是一个函数（这里的函数不是之前写的函数调用的那个函数，而是数学中的函数式），它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。（时间复杂度越大，运行水时间越长）。

        但是我们为什么不直接讨论快速排序执行多少时间、冒泡排序执行多少时间呢？原因在于具体怎么执行与自己的机器（硬件）有关，硬件配置不一样，就不能比较具体执行的时间。因此，我么需要一套与环境因素（如硬件因素）无关的理论，也就是这里的时间复杂度。

请观察下面的代码，然后进行分析：

/********请计算一下Func1中++count语句总共执行了多少次？*********/
void Func1(int N)
{
    int count = 0;
    for (int i = 0; i < N ; ++ i)
    {
         for (int j = 0; j < N ; ++ j)
         {
         ++count;
         }
    }
 
    for (int k = 0; k < 2 * N ; ++ k)
    {
         ++count;
    }
    int M = 10;
    while (M--)
    {
         ++count;
    }
    printf("%d\n", count);
}

Func1 执行的基本操作次数 ：F（N）=N^2+2*N+10
N = 10              F(N) = 130，            N^2 = 100
N = 100            F(N) = 10210,           N^2 = 10000
N = 1000          F(N) = 1002010,       N^2 = 1000000

        从这个例子我们发现，当N越大（当N趋于无穷大时）,N^2对时间复杂度的结果影响最大。因此，我们选择大概估算（大O的渐进表示法）的方法，忽略掉2*N+10这一项，时间复杂度就可以表示为：F（N）=O（N^2）。当N很小的时候，认为时间复杂度一样，没有比较的意义，CPU主频很大。（CPU主频在 2.3 有详细介绍）

2.2 大O的渐进表示法

        大概估算是计算算法属于哪个量级（level）。

        大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。
推导大O阶方法：
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
使用大O的渐进表示法以后，Func1的时间复杂度为：F（N）=O（N^2）
        N = 10 F(N) = 100
        N = 100 F(N) = 10000
        N = 1000 F(N) = 1000000

        通过上面的分析，我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。
        另外有些算法的时间复杂度存在最好、平均和最坏情况：
 最坏情况：任意输入规模的最大运行次数(上界)
 平均情况：任意输入规模的期望运行次数
 最好情况：任意输入规模的最小运行次数(下界)
例如：在一个长度为N数组中搜索一个数据x
 最好情况：1次找到
 最坏情况：N次找到
 平均情况：N/2次找到
        在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)。

2.3 为什么O（n）使用最坏情况下的估算结果呢？

         在这种情况下，实际的结果要么就是估算的结果的惊喜，要么就刚好是最低预期结果，这是一种以防万一的心态，在预估了所有坏的可能后得到的方案。

2.4 CPU主频（拓展）

CPU主频，也称为时钟频率或时钟速度，是指中央处理单元(CPU)内部时钟的频率或速度。

        它表示了处理器每秒钟执行指令的次数，通常以赫兹(Hz)为单位表示，例如兆赫兹(MHz)或千兆赫兹(GHz)。主频是评估其性能和速度的一个重要指标之一。一般来说，较高的主频意味着处理器能够更快地执行指令，因此在一定程度上具有更高的性能。然而，主频并不是评估处理器性能的唯一因素，其他因素如微架构、核心数量、缓存大小、指令集等也会影响性能。需要注意的是，主频并不是唯一影响处理器性能的因素。不同型号的处理器可能在相同主频下表现出不同的性能，因为它们的架构和其他规格可能不同。因此，在选择计算机或处理器时，不仅要考虑主频，还要综合考虑其他因素，以确保满足你的性能需求。

（资料来自百度）

CPU主频也叫时钟频率，单位是MHz，用来表示CPU的运算速度。

        CPU的工作频率（主频）包括两部分：外频与倍频，两者的乘积就是主频。

        倍频的全称为倍频系数。CPU的主频与外频之间存在着一个比值关系，这个比值就是倍频系数，简称倍频。倍频可以从1.5一直到23以至更高，以0.5为一个间隔单位。外频与倍频相乘就是主频，所以其中任何一项提高都可以使CPU的主频上升。由于主频并不直接代表运算速度，所以在一定情况下，很可能会出现主频较高的CPU实际运算速度较低的现象。因此主频仅仅是CPU性能表现的一个方面，而不代表CPU的整体性能 。

        处理器主频以每秒处理器周期可运行的百万次计算。通常，具有较高MHz或GHz的处理器能够提高电脑运行创新、娱乐、通信和生产力应用的性能。但主频只是影响系统整体性能的一个方面，主频高的机器整体性能并非就一定高。
                        
（声明：此段文本复制自博客：http://t.csdnimg.cn/FGGi7）

        简而言之，CPU主频反映了在一个周期内大概能执行多少指令主频越高，CPU的处理速度越快。CPU性能再怎么差，它每秒的运算速度也能运行上亿次。可以利用clock函数验证：

#include <time.h>
 
int main()
{
	int begin1 = clock();
	int n = 100000000;
	int x = 10;
	for (int i = 0; i < n; i++)
	{
		++x;
	}
	int end1 = clock();
 
	printf("%d\n", x); 
	printf("程序运行时间%d ms\n", end1 - begin1);
 
	return 0;
}

​

如果结果为0ms说明中间的时间消耗小于1ms，而不是没有时间消耗。

        C语言中的函数clock()，它可以捕捉从程序开始运行到clock()被调用时所耗费的时间。两个clock()函数的返回值相减，就可以计算两个函数之间的程序运行所消耗的大概时间(ms)了。我么可以利用它来大致测试一下电脑的性能。而且，release版本做了优化，因此时间比Debug版本稍短。

​

2.5 常见的时间复杂度量级

2.6 重要时间复杂度计算

2.6.1 冒泡排序的时间复杂度 O（n^2）

        F（n）=（n-1）+ (n-2) + (n-3)+……+3+2+1=n*（n-1）/2 （可以根据两个数比较的次数来写）, 时间复杂度为：O（n^2）。注意不能直接数循环的个数。

// 计算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;
    }
}

2.6.2 qsort函数的时间复杂度O（n*logn）

qsort函数的时间复杂度为： O（n*logn）

2.6.3 二分查找的时间复杂度

        折半查找：n，n/2，n/2/2，……，n/2/2/……/2（查找了x次就除以x个2）,2^x=N，所以x=logN（省略底数2）。最坏情况：查找区间只剩一个数或者找不到。O（logN）

// 计算BinarySearch的时间复杂度
int BinarySearch(int* a, int n, int x)
{
	assert(a);
	int begin = 0;
	int end = n - 1;
	// [begin, end]：begin和end是左闭右闭区间，因此有=号 
    //保持左闭右闭区间（保持不变）
    while (begin <= end)//begin=end，还有一个数
	{
		int mid = begin + ((end - begin) >> 1);//此写法可以防止溢出
		if (a[mid] < x)
			begin = mid + 1;//因为签】前一次比较中，mid已经比较过了
		else if (a[mid] > x)
			end = mid - 1;//end是mid-1
		else
			return mid;
	}
	return -1;
}
 
//写法二：
int BinarySearch(int* a, int n, int x)
{
    assert(a);
    int begin = 0;
    int end = n - 1;
    // [begin, end)  ->保持左闭右开区间
    while(begin<end)
    {
        //int mid = begin + ((end - begin) >> 1);//防止溢出（begin+end值可能很大）
        //也可以写成
        int mid = (begin + end)/2;(不能防止溢出)
        if (a[mid] < x)
            begin = mid + 1;
        else if (a[mid] > x)
            end = mid;//这里变成end=mid,而不是 mid-1
        else
            return mid;
    }
    return -1;
}
 
 
 

        二分查找：O（logN），随着N的增长，O（logN）变化不大；暴力查找：O（N），随着N的增长，O（N）变化很大。

        缺点：二分查找外强中干，在实际中不太实用，需要排序、而且数组结构不方便插入删除数据（会造成数据整体的挪动）。

2.6.4  strchr函数的时间复杂度

// 计算strchr的时间复杂度？
const char * strchr ( const char * str, int character );

        在一个字符串中查找一个字符，它的实现过程就相当于如下的代码：

while (*str)
{
	if (*str == character)
		return str;
	else
		++str;
}

        最好情况：O（1），最坏情况：O（n），平均情况：O（（1+2+3+……+n）/n））。所以时间复杂度为O（n）。

        时间复杂度的意义：帮助我们对比几种解决方法孰优孰劣。 

三、 常见时间复杂度的举例

1、O（n）只看循环次数，且系数对结果影响不大

        F（n）=2*n+10 , O（n）而不是O（2*n）。F（n）相当于只看循环次数,要去掉系数2（即使这个系数是200也要去掉）,系数对结果影响不大，n无穷大时，n和2*n没有区别。

// 计算Func2的时间复杂度？
void Func2(int N)
{
 int count = 0;
 for (int k = 0; k < 2 * N ; ++ k)
 {
 ++count;
 }
 int M = 10;
 while (M--)
 {
 ++count;
 }
 printf("%d\n", count);
}

2、O（n）可以用多个未知数表示

        F（n）=M+N,  O（M+N）或O（max(M,N)。在时间复杂度，经常使用N作为未知数，也可以使用其它符号来表示未知数。如果M远大于N，O(M)；如果如果N远大于M，O(N)。不一定只有一个未知数。

// 计算Func3的时间复杂度？
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);
}

3、F（n）= 常数,  O（1）

        时间复杂度是O（1），而不是O（100）。没有未知数而只有常数次，则时间复杂度为  O（1）。

// 计算Func4的时间复杂度？
void Func4(int N)
{
 int count = 0;
 for (int k = 0; k < 100; ++ k)
 {
 ++count;
 }
 printf("%d\n", count);
}

4、单身狗题目回顾（为下一道题做铺垫）

5、力扣--17.04. 消失的数字

        题目描述：数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？

思路1：先排序（冒泡排序、qsort快速排序）再查找，如果前一个值(b)不等于后一个值(a) +1，那么前一个值(b)就是消失的数字。（由于时间复杂度，现可以直接抛弃该思路）（排序：a，b; a+1==b），但时间复杂度不符合要求。

思路2：先将0~N进行求和，然后再依次减去数组中值，剩下的值就是消失的数字。时间复杂度为O（N）。（缺陷：N太大，存在溢出风险）

int missingNumber(int* nums, int numsSize){
    int N = numsSize;//0~n一共n+1个数，但缺了1个数，一共n个数
    int ret = (0 + N) * (N + 1) / 2;//计算出0~n的总和
    for(int i = 0; i < numsSize; ++i)//
    {
	    ret -= nums[i];//总和减去数组中值
    }
    return ret;
}

思路3：按位异或（相同为0，相异为1）（有点类似于单身狗的那道题）。O（n）

int missingNumber(int* nums, int numsSize){
    int N = numsSize;
    int x = 0;
    for(int i = 0; i < numsSize; ++i)//numsSize是少了1的，9个数
    {
        x ^= nums[i];//0和任何数异或均是任何数
    }  
    for(int j = 0; j <= N; ++j)//这里有n个数，10个数
    {
        x ^= j;
    }
    return x;
}

6、力扣--189. 轮转数组

        题目描述：给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。 

分析：需要一个循环两个嵌套，时间复杂度应该是：O（k*N）。

思路1：暴力求解（用只管的方式直接解 决问题，不用太多技巧）

        表达式为：F（N）= （N-1）*（N-1）；O（k * N）

        如果k为7或者7的倍数次,旋转7次或者7的倍数次，其实就是旋转到原来的样子（相当于不旋转）；如果旋转10次，就相当于旋转了3次。所以真实的旋转次数为 k % = N ;在最好情况下，即没有旋转，k % N = 0 , O（1）;在最坏情况下K（N）=N*(N-1)， k % N = N-1，O（N^2）,旋转N-1次，。

        值得注意的是：时间复杂度必须要计算调用的其它方法所花的时间消耗。

void rotate(int* nums, int numsSize, int k) 
{
    k%=numsSize;
    while(k--)//k最大为n-1，k--走了k次，所以这里走了n-1次
    {
        //旋转一次      画图是最好的分析方法
        int tmp = nums[numsSize-1];//最后一个数保存起来
        for(int i =numsSize-2;i >= 0;i--)//起始位置在n-2（numsSize-2），结束情况：i >= 0
        {
            nums[i+1] = nums[i];//中间过程
        }
        nums[0] = tmp;
    }//但是用这种方法不能通过，超出时间限制（不能O（N^2））
}
 
//前n-1个数往后挪
//循环分析：循环就三个过程，起始情况、中间过程、结束情况

        思路2：三段逆置  O（N）

代码如下： 

void reverse(int*  a,int left,int right)
{
    //三段逆置一定要画图,下标标明
    while(left<right)//一段区间，左右往中间走，未相遇，交换值
    {
        int tmp =a[left];
        a[left] = a[right];
        a[right] = tmp;
        ++left;
        --right;
    }
}
 
void rotate(int* nums, int numsSize, int k) {
    k%= numsSize;
 
    reverse(nums,0,numsSize-k-1);//前n-k个数，最后一个下标n-k-
    reverse(nums,numsSize-k,numsSize-1);
    reverse(nums,0,numsSize-1);
}

strncpy是针对字符串的，在这里不合适。
 

7、对数时间复杂度常见出现形式

        时间复杂度O（logN）

void func(int n)
{
    int x = 0;
    for (int i = 1; i < n; i *= 2)
    {
        ++x;
    }
    printf("%d\n", x);
}
int main()
{
    func(8);
    func(1024);
    func(1024*1024);
    return 0;
}

        分析：1*2*2*……*2 = N；假设循环走x次，就是x个2相乘，2^x=N，两边同时取对数，得到 。时间复杂度就是O（）。因为写的时候需要支持专业公式，否则不好写底数。为了方便 省略了底数2，直接写成了，但是其他的就不能省略且其他底数的很少出现。

8、阶乘递归的时间复杂度

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

        每次调用函数都是O（1）的复杂度，调用N次就是O（N）的复杂度，而不是O（N！）。如果变式：时间复杂度为O（N^2）。 

 
//变式：
// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
     if(0 == N)
     return 1;
     for(int i = 0; i <N;++i)
    {
        //……
    }
     return Fac(N-1)*N;
}

        总结：递归时间复杂度为所有递归调用消耗次数（相当于运算次数）的累加。

9、斐波那契递归和非递归的时间复杂度

        斐波那契递归非递归的时间复杂度O（N^2）

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

        最左侧会逐步减少到Fib（1），有N层，但是右侧未必能走到N层，所以呈现的三角形并不是等腰三角形，但是不影响最终的量级，大O阶表示时间复杂度O（N^2） 。分析过程如下图：

         斐波那契非递归（斐波那契数列的优化）的时间复杂度 ：

// 1  1  2  3  5  8....
// 时间复杂度：O(N)（很大的优化）
long long Fib(size_t N)
{
	long long f1 = 1;
	long long f2 = 1;
	long long f3 = 0;
	for (size_t i = 3; i <= N; i++)
	{
		f3 = f1 + f2;
		f1 = f2;
		f2 = f3;
	}
 
	return f3;
}

        其实斐波那契数列没什么特别的实用意义，因为数据稍稍大点就计算不出结果了。（50都不得行了）。此外，还可以使用字符串进行存储（大树运算）。

四、空间复杂度

4.1 空间复杂度定义 

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

4.2 空间复杂度例题

        1、冒泡排序的空间复杂度

        变量个数：3（常数个），所以空间复杂度为O（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;
    }
}

         2、  轮转数组另一个解法（空间复杂度）

        不用三段逆置的方法，重新创建一个数组，后k个旋转在前面，再把前n-k个拷贝到后面去 ，最后再将最终结果拷贝到原来的位置。此时，新创建的N个数组就是为了解决此问题而创建的，它就需要计算空间，空间复杂度就是O（N）。

最后的代码如下，代码中使用了变长数组：

void _rotate(int* nums, int numsSize, int k, int* tmp)
{
	k %= numsSize;
	int n = numsSize;
 
	memcpy(tmp, nums + n - k, sizeof(int) * k);
	memcpy(tmp+k, nums, sizeof(int) * (n-k));
	memcpy(nums,tmp, sizeof(int) * (n));
}
 
void rotate(int* nums, int numsSize, int k)
{
	int tmp[numsSize];
	_rotate(nums, numsSize, k, tmp);
}

        3、阶乘递归的空间复杂度

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

4、斐波那契数列的空间复杂度为：

         常见的空间复杂度中只有三种：O（1）、O（N）、O（N^2）（比如二维数组）。

        创作不易，喜欢的uu三连支持一下叭！