算法复杂度

在学习了c语言相关的知识后，接下来我们就要进行数据结构的学习，在此学习的是初阶数据结构，我们将掌握顺序表、链表、栈和队列、⼆叉树、常见排序算法等内容；高阶数据结构如图、哈希表、红黑树等数据结构将在C++中学习。初阶数据结构中我们将继续使用C语言来实现基础的数据结构，在掌握数据结构的同时巩固了刚结束的C语法知识，因此在学习初阶数据结构过程要求我们要拥有扎实的c语言基础，如果还未完成c语言基础知识的学习或者是对c语言还有困惑，可以继续阅览c语言基础知识，接下来就开始本篇的学习吧！

1.数据结构前言

在学习数据结构前，首先要了解数据结构和算法分别是什么
数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。没有一种单一的数据结构对所有用途都有用，所以我们要学各式各样的数据结构，如：线性表、树、图、哈希等

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

以上关于数据结构和算法的概念简单来说就是：数据结构是一个载体可以承数据，而算法是一个工具能让我们更好的取出数据，管理数据。
因此要知道数据结构和算法不分家，有数据结构的地方一定会用到算法，而用到算法的数据一定存储在相关的数据结构内。

2. 算法效率

例如在解决一道题时，通常会有许多种解法，那么在不同的解法也就是在不同的算法中是如何来衡量其好坏的呢？

例如以下OJ题
旋转数组

这时如果每轮转一次就将数组元素都整体向后移动一位，要轮转几次就使用循环重复数组的移动，以上操作用两个循环的嵌套理论上是可以解决这道算法题的

void rotate(int* nums, int numsSize, int k) 
{
    while(k--)
    {
        int end = nums[numsSize-1];
        for(int i = numsSize - 1;i > 0 ;i--)
        {
          nums[i] = nums[i-1];
        }
        nums[0] = end;
    }
}

但是在提交时就会出现以下问题，这就说明我们这种解法是存在缺陷的，那么这种算法在该题中为什么会出现超出时间限制这种问题呢？
接下来我们就要来了解复杂度

3.复杂度

3.1复杂度的概念

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好
坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量⼀个算法运行行所需要的额外空间。在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注⼀个算法的空间复杂度。但是这不代表我们在编写代码的过程中完全不在乎空间复杂度，只是相比时间的消耗，空间的消耗不再那么在乎，有时会使用空间来换取时间。

3.2时间复杂度

定义：在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它定量描述了该算法的运行时间。时间复杂度是衡量程序的时间效率，那么为什么不去计算程序的运行时间呢？

例如以下代码：
#include<stdio.h>
#include<time.h>
int main()
{
	int begin = clock();
	int count = 0;
	for (int i = 0; i < 100000000; i++)
	{
		count++;
	}
	int end = clock();
	printf("Time:%d", end - begin);

	return 0;
}
以上我们使用库函数clock来得到程序运行到函数位置的时间，单位是毫秒，而将以上代码中的两的clock函数相减就可以的得到两个函数之间代码的运行时间
以下是以上代码的输出结果

以上输出结果是在Debug的模式下运行的，因为Debug模式下会加载一些调试信息，所以会使得程序的运行速度受到影响，如果在Release模式下以上代码输出结果又会变为以下形式

通过以上示例就可以发现编译的环境会对程序的运行时间造成影响，
所以在求程序的时间效率，那么为什么不去计算程序的运行时间的原因如下所示

1. 因为程序运行时间和编译环境和运行机器的配置都有关系，比如同一个算法程序，用一个老编译器进行编译和新编译器编译，在同样机器下运行时间不同。
2. 同一个算法程序，用一个老低配置机器和新高配置机器，运行时间也不同。
3. 并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估。

算法的时间复杂度的函数式T(N)其实计算的是程序的执行次数，这是为什么呢？
因为在程序当中每条语句的运行时间是和编译环境；运行环境等都相关的，所以程序当中每条语句的运行时间是不确定的，而程序的运行次数是固定的与所处的环境等无关，假设每句指令执行时间基本⼀样(实际中有差别，但是微乎其微)，那么执行次数和运行时间就是等比正相关，所以使用程序每条语句的运行次数来计算程序的时间复杂度

在了解了T(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;
    }
}
通过分析就可以分析Fun1中的++count语句总共执行次数函数如下
$T(N)=N^{2}+ 2 N + 10$

这时在该公式当中，N取10，100，1000时，T(N)的值如下

在这当中就可以发现N^2对函数最终的值影响最大，其他的参数对结果的影响较小
实际中我们计算时间复杂度时，计算的也不是程序的精确的执行次数，精确执行次数计算起来还是很麻烦的(不同的一句程序代码，编译出的指令条数都是不⼀样的)，计算出精确的执行次数意义也不大，因为我么计算时间复杂度只是想比较算法程序的增长量级，也就是当N不断变大时T(N)的差别，上面我们已经看到了当N不断变大时常数和低阶项对结果的影响很小，所以我们只需要计算程序能代表增长量级的大概执行次数，复杂度的表示通常使用大O的渐进表示法

3.2.1 大O的渐进表示法

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号

💡 推导大O阶规则
1. 时间复杂度函数式T(N)中，只保留最高阶项，去掉那些低阶项，因为当N不断变大时，低阶项对结果影响越来越小，当N无穷大时，就可以忽略不计了。
2. 如果最高阶项存在且不是1，则去除这个项目的常数系数，因为当N不断变大，这个系数对结果影响越来越小，当N无穷大时，就可以忽略不计了。

3. T(N)中如果没有N相关的项目，只有常数项，用常数1取代所有加法常数。

通过以上的规则1就可以求出Fun1的时间复杂度为 $O(N^{2})$

3.2.2 时间复杂度计算示例

示例1

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

Fun2执行的基本次数
T(N)=2N+10

通过大O渐进表示法中的规则1和2就可以得出以上Fun2的时间复杂度为 $O(N)$

示例2

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

Fun3执行的基本次数
T(N)=M+N

通过大O渐进表示法中的规则1就可以得出以上Fun3的时间复杂度会出现3种情况
若M>>N, $O(N)=M$
若M<<N, $O(N)=N$
若M==N， $O(N)=M+N$

示例3

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

Fun4执行的基本次数
T(N)=100

通过大O渐进表示法中的规则1就可以得出以上Fun4的时间复杂度为
$O(N)=1$

示例4

// 计算strchr的时间复杂度？
const char * strchr ( const char* str, int character)
{
    const char* p_begin = str;
    while (*p_begin != character)
    {
        if (*p_begin == '\0')
        return NULL;
        p_begin++;
    }
    return p_begin;
}

strchr执行的基本操作次数：
T(N)取决于要查找的字符在字符串中的位置，会出现以下三种情况

1.要查找的字符在字符串的头部
T(N)=1
2.要查找的字符在字符串的尾部
T(N)=N
3.要查找的字符在字符串的中间
T(N)=N/2

因此strchr的时间复杂度分为：
最好情况 $O(N)=1$
最坏情况 $O(N)=N$
中间情况 $O(N)=\frac{N}{2}$

💡 总结通过上面我们会发现，有些算法的时间复杂度存在最好、平均和最坏情况。
最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界) 大O的渐进表示法在实际中一般情况关注的是算法的上界，也就是最坏运行情况。

示例5

// 计算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)中学习了冒泡排序的原理，尝试了试着去实现冒泡排序，以上的BubbleSort就是冒泡排序的实现代码，现在我们要计算出这段代码的时间复杂度

首先要来分析以上代码，在排序过程中如果数字串一开始是就是有序的，那么外层的for循环就就只需要进行一次也就是只要进行一趟排序，内层循环进行每趟内部的遍历，因此时间复杂度就为 $O(N)$

如果数字串一开始不是有序的，那么外层的for循环就会进行end趟，内层循环每趟会进行i-1次

以上就可以得出趟数和每趟内部的比较次数呈等差数列，T(N)=N*N/2
因此时间复杂度就为 $O(N)=N^{2}$
因此在以上两种情况中BubbleSort的时间复杂度取最差情况为： $O(N)=N^{2}$

示例6

void func5(int n)
{
    int cnt = 1;
    while (cnt < n)
    {
        cnt *= 2;
    }
}

在以上代码中例如n为10时，cnt在循环时的变化如下所示,在进行完第四次循环后cnt=16

现在定义一个x变量来表示循环次数，通过以上示例就可以得出一个规律式 $2^{x}=N$ ,对表达式两边同时取对数就可以得到 $x=\log_{2}N$

因此func5的时间复杂度取最差情况为： $O(N)=\log_{2}N$

注意 log2 n 、 log n 、 lg n 的表示当n接近无穷大时，底数的大小对结果影响大。因此，一般情况下不管底数是多少都可以省略不写，即可以表⽰为 log n 不同书籍的表达方式不同，以上写法差别不大，建议使用 log n

示例7

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

Fac内每一次调用函数时间复杂度为 $O(N)=1$ ,在Fac函数中存在n次递归，所以Fac的时间复杂度为 $O(N)=N$

3.3空间复杂度

在了解了时间复杂度后继续来了解空间复杂度

空间复杂度也是一个数学表达式，是对⼀个算法在运行过程中因为算法的需要额外临时开辟的空间。空间复杂度不是程序占用了多少bytes的空间，因为常规情况每个对象大小差异不会很大，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。

注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定

3.3.1 空间复杂度计算示例

示例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;
    }
}

以上函数中需要额外开辟的空间只要以下图示的3个

通过大O的渐进表示法的规则就可以得出Bubble的空间复杂度为 $O(N)=1$

示例2

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

Fac递归调用了N次，额外开辟了N个函数栈帧，每个栈帧使用了常数个空间
因此空间复杂度为： $O(N)=N$

3.4. 常见复杂度对比

4. 复杂度算法题

旋转数组

现在我们就来分析为什么之前的解法会出现超出时间限制的问题

以上代码的时间复杂度为 $O(N)=N^{2}$

在复杂度的对比图中就可以发现N^2函数斜率很大，增长速度很快，所以这种算法会在数据很多时超出时间限制，因此我们要用时间复杂度更低的算法来解决本题

解法1

申请新数组空间，先将后k个数据放到新数组中，再将剩下的数据挪到新数组中

void rotate(int* nums, int numsSize, int k)
{
    int arr[numsSize];
    for(int i=0;i<numsSize;i++)
    {
        arr[(i+k)%numsSize]=nums[i];
    }
    for(int i=0;i<numsSize;i++)
    {
        nums[i]=arr[i];
    }  
}

这时这种算法的时间复杂度就为O(N),但申请了新的空间空间复杂度就从O(1)变为了O(N),这种做法是使用空间来换取时间，那么是否有不让时间复杂度提升的同时空间复杂度也为O(1)的做法呢？

解法2

例如要将1234567向右轮转 3 步

这时就先将前n-k个逆置，后再将后k个逆置，之后再将整体逆置一遍就完成了1234567向右轮转 3 步

以下就是这种算法的代码的实现，创建了一个reverse函数来实现逆置，这时在rotate函数内只要传相应的函数参数就可以实现数字串中要逆置的部分，在这种算法中函数的空间复杂度为O(1)

void reverse(int* nums,int left,int right)
{
    while(left<right)
    {
        int tmp=nums[left];
        nums[left]=nums[right];
        nums[right]=tmp;
        right--;
        left++;
    }  
}

void rotate(int* nums, int numsSize, int k) 
{
    k=k%numsSize;
    reverse(nums,0,numsSize-k-1);
    reverse(nums,numsSize-k,numsSize-1);
    reverse(nums,0,numsSize-1);
}

以上就是算法复杂度篇章的全部内容了，希望能得到你的点赞，收藏，感谢你的观看！！！