1. 时间复杂度函数式T(N)中，只保留最⾼阶项，去掉那些低阶项，因为当N不断变⼤时，低阶项对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了。
   平均情况：任意输⼊规模的期望运⾏次数。组织数据的⽅式，指相互之间存在⼀种或多种特定关系的数据元素的集合。平均和最坏情况。

   3.3.5 ⽰例5

   // 计算BubbleSort的时间复杂度？voidBubbleSort(int*a,intn){assert(a);for(size_tend =n;end >0;--end){intexchange =0;for(size_ti =1;i <end;++i){if(a[i-1]>a[i]){Swap(&a[i-1],&a[i]);exchange =1;}}if(exchange ==0)break;}}

   BubbleSort的时间复杂度取最差情况为： O(N2 )。
   注意：函数运⾏时所需要的栈空间(存储参数、
   how学好数据结构？（这可是干货，嘿嘿）
   1，死磕代码。

   5.常⻅复杂度对比

   
   

   6. 复杂度算法题

   
   思路1
   时间复杂度 O(n2 )
   循环K次将数组所有元素向后移动⼀位（代码不通过原因:时间超时了）

   voidrotate(int*nums,intnumsSize,intk){while(k--){intend =nums[numsSize-1];for(inti =numsSize -1;i >0;i--){nums[i]=nums[i-1];}nums[0]=end;}}

   思路2：
   空间复杂度 O(n)
   申请新数组空间，先将后k个数据放到新数组中，再将剩下的数据挪到新数组中。
   ⼤O的渐进表⽰法在实际中⼀般情况关注的是算法的上界，也就是最坏运⾏情况。

   3.3.4 ⽰例4

   // 计算strchr的时间复杂度？constchar*strchr(constchar*str,intcharacter){constchar*p_begin =s;while(*p_begin !=character)//三种范围区间{if(*p_begin =='')returnNULL;p_begin++;}returnp_begin;}

   最好情况： O(1)
   最坏情况： O(N)
   平均情况： O(N)
   解析：
   strchr执⾏的基本操作次数：
   1）若要查找的字符在字符串第⼀个位置，则：T (N) = 1
   2）若要查找的字符在字符串最后的⼀个位置，则：T (N) = N
   3）若要查找的字符在字符串中间位置，则：T (N) =2N
   因此：strchr的时间复杂度分为：
   最好情况： O(1)，最坏情况： O(N)，平均情况： O(N)。BubbleSort额外申请的空间有exchange等有限个局部变量，使用了常数个额外空间。图、

   3.3.6 ⽰例6

   voidfunc5(intn){intcnt =1;while(cnt <n){cnt *=2;}}

   func5的时间复杂度取最差情况为：O(log2 n);
   解析：
   假设执⾏次数为 x ，则 2x = n；
   因此执⾏次数： x = log n。
   空间复杂度计算规则基本跟实践复杂度类似，也使⽤⼤O渐进表⽰法。哈希等。局部变量、树、2，画图＋思考。⼀些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定。
   解析：
   T (N) = 100（for循环执行次数为100）根据推导规则第1条得出Func2的时间复杂度为： O(1)。

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

   2.算法效率

   2.1复杂度的概念

   (1).衡量⼀个算法的好坏，⼀般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

   文章目录

   • 算法复杂度
   • • 1.数据结构
     • • 1.1 数据结构（数据的管理）
       • 1.2算法（取，管理数据）
     • 2.算法效率
     • • 2.1复杂度的概念
     • 3.时间复杂度
     • • 3.1时间复杂度是衡量程序的时间效率，那么为什么不去计算程序的运⾏时间呢？
       • 3.2⼤O的渐进表示法
       • 3.3 时间复杂度计算⽰例
       • • 3.3.1 ⽰例1
         • 3.3.2 ⽰例2
         • 3.3.3 ⽰例3
         • 3.3.4 ⽰例4
         • 3.3.5 ⽰例5
         • 3.3.6 ⽰例6
         • 3.3.7 ⽰例7
     • 4.空间复杂度
     • • 4.1 空间复杂度计算⽰例
       • • 4.1.1 ⽰例1
         • 4.1.2 ⽰例2
     • 5.常⻅复杂度对比
     • 6. 复杂度算法题
   • 总结：

   算法复杂度

   1.数据结构

   1.1 数据结构（数据的管理）

   数据结构(Data Structure)是计算机存储、

   3.时间复杂度

   在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它定量描述了该算法的运⾏时间。

   3.3.7 ⽰例7

   // 计算阶乘递归Fac的时间复杂度？longlongFac(size_tN){if(0==N)return1;returnFac(N-1)*N;}

   阶乘递归的时间复杂度为： O(n).
   解析:
   调⽤⼀次Fac函数的时间复杂度为 O(1);⽽在Fac函数中，存在n次递归调⽤Fac函数.

   4.空间复杂度

   空间复杂度是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。

   4.1 空间复杂度计算⽰例

   4.1.1 ⽰例1

   // 计算BubbleSort的时间复杂度？voidBubbleSort(int*a,intn){assert(a);for(size_tend =n;end >0;--end){intexchange =0;//局部变量for(size_ti =1;i <end;++i){if(a[i-1]>a[i]){Swap(&a[i-1],&a[i]);exchange =1;}}if(exchange ==0)break;}}

   空间复杂度为 O(1)；
   解析：
   函数栈帧在编译期间已经确定好了，只需要关注函数在运⾏时额外申请的空间。
   最好情况：任意输⼊规模的最⼩运⾏次数(下界)。

   3.3.3 ⽰例3

   // 计算Func4的时间复杂度？voidFunc4(intN){intcount =0;for(intk =0;k <100;++k)//执行次数为100{++count;}printf("%d\n",count);}

   Func2的时间复杂度为： O(1)。
   从这道例题得出结论：
   通过上⾯我们会发现，有些算法的时间复杂度存在最好、数据结构eg：
   线性表、
   解析：
   Fac递归调⽤了N次，额外开辟了N个函数栈帧，每个栈帧使⽤了常数个空间。

   1.2算法（取，管理数据）

   算法(Algorithm):就是定义良好的计算过程，他取⼀个或⼀组的值为输⼊，并产⽣出⼀个或⼀组值作为输出。

   4.1.2 ⽰例2

   // 计算阶乘递归Fac的空间复杂度？longlongFac(size_tN){if(N ==0)return1;returnFac(N-1)*N;//递归调用了N次}

   空间复杂度为： O(N)。
   解析：
   BubbleSort执⾏的基本操作次数：1）若数组有序，则：T (N) = N。eg:O(100)= O(1);用O（1）来表示常数。
   (2).时间复杂度主要衡量⼀个算法的运⾏快慢，⽽空间复杂度主要衡量⼀个算法运⾏所需要的额外空间。

   3.2⼤O的渐进表示法

   ⼤O符号（Big O notation）：是⽤于描述函数渐进⾏为的数学符号。newArr[(i + k) % numsSize] = nums[i];（关键）

   voidrotate(int*nums,intnumsSize,intk){intnewArr[numsSize];for(inti =0;i <numsSize;++i){newArr[(i +k)%numsSize]=nums[i];//这一部超妙}for(inti =0;i <numsSize;++i){nums[i]=newArr[i];}}

   思路3：如下图，参考下面代码及注释
   

   空间复杂度 O(1)

   voidreverse(int*nums,intleft,intright){//函数定义用逗号while(left<right){inttmp =nums[left];nums[left]=nums[right];nums[right]=tmp;left++;right--;}}voidrotate(int*nums,intnumsSize,intk){k =k%numsSize;//前n-k个数据逆置reverse(nums,0,numsSize-k-1);//函数调用用逗号//后k个数据逆置reverse(nums,numsSize-k,numsSize-1);//整体逆置reverse(nums,0,numsSize-1);}

   总结：

   以上就是关于数据结构中算法复杂度的全部内容了，写的超详细，博主写了两天，喜欢的兄弟们，可以一键三连。

3.3 时间复杂度计算⽰例

3.3.1 ⽰例1

// 计算Func2的时间复杂度？voidFunc2(intN){intcount =0;for(intk =0;k <2*N ;++k)//FOR循环执行次数为2N{++count;}intM =10;while(M--)//while循环次数为10{++count;}printf("%d\n",count);}

Func2的时间复杂度为： O(N)
解析：Func2执⾏的基本操作次数：T (N) = 2N + 10,(2N:FOR循环执行次数为2N；10：while循环次数为10)根据推导规则第3条得出,Func2的时间复杂度为： O(N).

3.3.2 ⽰例2

// 计算Func3的时间复杂度？voidFunc3(intN,intM){intcount =0;for(intk =0;k <M;++k)//FOR循环执行次数为M{++count;}for(intk =0;k <N ;++k)//第二个for循环循环次数为N{++count;}printf("%d\n",count);}

Func2的时间复杂度为： O(N)。