数据结构与算法—算法复杂度

前言

学习数据结构小妙招：死磕代码 + 画图 + 无限思考
书籍推荐：《数据结构》—严蔚敏 （c版）
        《 算法导论》—托马斯-科尔曼
        《大话数据机构》—程杰
有时间的大家可以选择性观看

目录

数据结构

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

算法

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

复杂度的概念

算法在编写成可执⾏程序后，运⾏时需要耗费时间资源和空间(内存)资源。因此衡量⼀个算法的好坏，⼀般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。 时间复杂度主要衡量⼀个算法的运⾏快慢，⽽空间复杂度主要衡量⼀个算法运⾏所需要的额外空间。在计算机发展的早期，计算机的存储容量很⼩。所以对空间复杂度很是在乎。但是经过计算机⾏业的迅速发展，计算机的存储容量已经达到了很⾼的程度。所以我们如今已经不需要再特别关注⼀个算法的空间复杂度。

这里来看一道力扣上的题

虽然在本地测试能够成功，但提交代码显示错误，显示超出时间限制，这说明时间复杂度不好，所以接下来来看看时间复杂度和空间复杂度。

时间复杂度

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

1. 因为程序运⾏时间和编译环境和运⾏机器的配置都有关系，⽐如同⼀个算法程序，⽤⼀个⽼编译 器进⾏编译和新编译器编译，在同样机器下运⾏时间不同。
2. 同⼀个算法程序，⽤⼀个⽼低配置机器和新⾼配置机器，运⾏时间也不同。
3. 并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估。 那么算法的时间复杂度是⼀个函数式T(N)到底是什么呢？***这个T(N)函数式计算了程序的执⾏次数。***通过c语⾔编译链接章节学习，我们知道算法程序被编译后⽣成⼆进制指令，程序运⾏，就是cpu执⾏这些编译好的指令。那么我们通过程序代码或者理论思想计算出程序的执⾏次数的函数式T(N)，假设每句指令执⾏时间基本⼀样(实际中有差别，但是微乎其微)，那么执⾏次数和运⾏时间就是等⽐正相关，这样也脱离了具体的编译运⾏环境。执⾏次数就可以代表程序时间效率的优劣。⽐如解决⼀个问题的算法a程序T(N)=N，算法b程序T(N)=N^2，那么算法a的效率⼀定优于算法b。

看到例题

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

我们来计算一下count的时间复杂度

这里是嵌套循环所以是N的平方

所以最后的时间复杂度是N的平方 + 2N + 10

但是实际中我们计算时间复杂度时，计算的也不是程序的精确的执⾏次数，精确执⾏次数计算起来还是很⿇烦的(不同的⼀句程序代码，编译出的指令条数都是不⼀样的)，计算出精确的执⾏次数意义也不⼤，因为我们计算时间复杂度只是想⽐较算法程序的增⻓量级，也就是当N不断变⼤时T(N)的差别，上⾯我们已经看到了当N不断变⼤时常数和低阶项对结果的影响很⼩，所以我们只需要计算程序能代表增⻓量级的⼤概执⾏次数，复杂度的表⽰通常使⽤⼤O的渐进表⽰法。

大O的渐进表示法

在这里插入图片描述

时间复杂度计算案例

// 计算strchr的时间复杂度？ 
const char *strchr(const char *str, int character) {
    const char *p = str;
    while (*p != '\0') {  // 遍历字符串
        if (*p == (char)character) {  // 检查是否匹配
            return p;
        }
        p++;
    }
    // 检查 character 是否是 '\0'
    if ((char)character == '\0') {
        return p;  // 返回字符串的结束符位置
    }
    return NULL;  // 未找到
}

1. 最坏情况（未找到或匹配 '\0'）：
   • 需要遍历整个字符串，直到遇到 '\0'。
   • 如果字符串长度为 n，则循环执行 n 次。
   • 时间复杂度：O(n)。
2. 最好情况（第一个字符匹配）：
   • 直接进入 if 并返回，无需继续遍历。
   • 时间复杂度：O(1)。
3. 平均情况：
   • 假设字符在字符串中均匀分布，平均需要检查 n/2 次。

⼤O的渐进表⽰法在实际中⼀般情况关注的是算法的上界，也就是最坏运⾏情况。

空间复杂度

空间复杂度也是⼀个数学表达式，是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。空间复杂度不是程序占⽤了多少bytes的空间，因为常规情况每个对象⼤⼩差异不会很⼤，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使⽤⼤O渐进表⽰法。注意：函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定。

学习了时间复杂度和空间复杂度的方法之后，再来看上述开始的那道题，再把代码拿出来

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

在这里插入图片描述

时间复杂度：在此处我们并不知道圈中他们具体大小，因为是嵌套循环按照最坏情况就是N的平方，所以会导致时间复杂度太大，导致代码不通过，我们需要想办法减小时间复杂度，看接下来的代码

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

申请新数组空间，先将后k个数据放到新数组中，再将剩下的数据挪到新数组中 这样我们的时间复杂度来到了N，但是空间复杂度也来到了N，但是当你提交代码会发现代码能够通过，所以减少时间复杂度成功，但我们在思考一下，有没有什么办法能够将空间复杂度减下去，看接下来代码

void reverse(int* nums,int begin,int end)
{
	 while(begin<end){
	 int tmp = nums[begin];
	 nums[begin] = nums[end];
	 nums[end] = tmp;
	 begin++;
	 end--;
 }
}
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);
}

空间复杂度O(1) •前n-k个逆置：4 3 2 1 5 6 7 • 后k个逆置：4 3 2 1 7 6 5 • 整体逆置：5 6 7 1 2 3 4

这些办法不是一蹴而就，都需要我们在不断的学习，思考，练习中才能熟练运用，想到办法。