数据结构之“算法的时间复杂度和空间复杂度”

                                                 🌹个人主页🌹：喜欢草莓熊的bear

                                                         🌹专栏🌹：数据结构

---

目录

前言

一、算法效率

1.1算法的复杂度概念

1.2复杂度的重要性

二、时间复杂度

2.1时间复杂度的概念

2.2大O的渐进表示法

2.3常见的时间复杂度例题计算

例题1

例题2

例题3

三、空间复杂度

3.1空间复杂度的概念

3.2大O的渐进表示法

3.3常见的空间复杂度例题计算

例题1

例题2

例题3

总结

---

前言

宝宝们，跟上bear的节奏继续进步！

今天我们学习的目标：

1.算法复杂度的理解

2.知道时间、空间复杂度的概念

3.学会使用大O表示法

4.计算常见复杂度例题

一、算法效率

1.1算法的复杂度概念

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

1.2复杂度的重要性

出现在面试题就大抵可以知道复杂度在这里的重要性了。

最容易想到的思路：先给数组排序，然后判断前一个数+1是否等于后一个值。不等于则返回前一个数+1。排序的复杂度是qsort  O（N*logN） 显然不符合。

 解决思路1：我们通过等差数列的求和公式得到总值，然后依次减去数组中的每个值。就可以找到消失的数字。但是有风险，N的值可能过大导致溢出

//f法1   Nt太大可能会溢出
int missingNumber(int* nums, int numsSize)
{
int N=numsSize;
int sum=(0+N)*(N+1)/2;
for(int i=0;i 0; --end)
 {
 int exchange = 0;
 for (size_t i = 1; i  a[i])
 {
 Swap(&a[i-1], &a[i]);
 exchange = 1;
 }
 }
 if (exchange == 0)
 break;
 }
}

例题2

这里我们发下先他新创建了一个指针（等价于数组），我们默认新创建的数组复杂度为N，还有一共变量i，O(N+1)空间复杂度化简为O(N)。

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