复杂度的讲解

数据结构可以简单理解为在内存中管理数据

它具有速度快  带电存储的特点（临时存储）

如何衡量一个算法的好坏

因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

时间复杂度主要衡量一个算法的运行快慢，

而空间复杂度主要衡量一个算法运行所需要的额外空间

1.时间复杂度

1.1时间复杂度的概念

算法的时间复杂度是一个表达式，算法中的基本操作的执行次数，为算法的时间复杂度

1.2 大O的渐进表示法

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

如何推导出O

1、用常数1取代运行时间中的所有加法常数。

2、在修改后的运行次数函数中，只保留最高阶项。

3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

那么前面的F(N)=N^2+2N+10 的复杂度也就是   O(N^2)

另外有些算法的时间复杂度存在最好、平均和最坏情况：

 最坏情况：任意输入规模的最大运行次数(上界)

 平均情况：任意输入规模的期望运行次数

 最好情况：任意输入规模的最小运行次数(下界)

例如：在一个长度为N数组中搜索一个数据x

 最好情况：1次找到

 最坏情况：N次找到

 平均情况：N/2次找到

在实际中表示时间复杂度一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

1.3关于时间复杂度的举例

例题一

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

例题二

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

例题三

void Func4(int N)
{int count = 0;for (int k = 0; k < 100; ++k){++count;}printf("%d\n", count);
}

例题四

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

例题五：冒泡排序算法的时间复杂度

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

例题六：二分查找

一定要注意二分查找的前提是有序

int BinarySearch(int* a, int n, int x)
{assert(a);int begin = 0;int end = n - 1;// [begin, end]：begin和end是左闭右闭区间，因此有=号while (begin <= end){int mid = begin + ((end - begin) >> 1);if (a[mid] < x)begin = mid + 1;else if (a[mid] > x)end = mid - 1;elsereturn mid;}return -1;
}

例题七：关于阶乘

long long Fac(size_t N)
{if (0 == N)return 1;return Fac(N - 1) * N;
}

例题八

例题九：斐波那契数

long long Fib(size_t N)
{if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);
}

1.4关于一道题目. - 力扣（LeetCode）消失的数字

这道题主要有两种解法

方法一：利用等差数列求和的方法找出消失的数字

int missingNumber(int* nums, int numsSize) {//numsSize就是最大的那个数，也就是缺失的数一定小于numsSizeint n = numsSize;//利用等差数列0,1,2,3,....n//   首项加尾项  再乘总项数  最后再除2int sum = (0+n) * (n+1) / 2;int i = 0;int sum1=0;for(i=0;i<n;i++){sum1=sum1+*(nums+i);}int rst =sum-sum1;printf("%d\n",rst);return rst;
}

方法二:利用异或符号来求出缺失的数字

int missingNumber(int* nums, int numsSize) {int i=0;int x=0;for(i=0;i<numsSize;i++)//numsize表示的是数组的元素个数如果是9那么就是0到9之间缺了一个元素{x=x^nums[i];}for(i=0;i<=numsSize;i++)//0到9之间的所有数字{x=x^i;}return x;
}

2.空间复杂度

2.1空间复杂度的概念

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时额外占用存储空间大小的量度

空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。

空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。

函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，

因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

2.2关于空间复杂度的举例

例题一：冒泡排序算法的空间复杂度

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

例题二：

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 <= n ; ++i){fibArray[i] = fibArray[i - 1] + fibArray [i - 2];}return fibArray;
}

例题三：

long long Fac(size_t N)
{if(N == 0)return 1;return Fac(N-1)*N;
}

例题四：

两道练习题

练习一： 旋转数组OJ链接：. - 力扣（LeetCode）

方法一：

这个方法因为超时而错误

​
void rotate(int* nums, int numsSize, int k) {int tmp = 0;int i = 0;while (k > 0){tmp = nums[numsSize - 1];for (i = 0; i < numsSize - 1; i++)//i从0到5{nums[numsSize - 1 - i] = nums[numsSize - 2 - i];}nums[0] = tmp;k--;}for (i = 0; i < numsSize; i++){printf("%d ", nums[i]);}
}​

方法二：

void fun(int* nums, int left, int right)
{while (left < right){int tmp = 0;tmp = nums[left];nums[left] = nums[right];nums[right] = tmp;left++;right--;}
}void rotate(int* nums, int numsSize, int k) {int N = numsSize;k = k % N;//先把前N-k个逆置fun(nums, 0, N - k - 1);//后k个逆置fun(nums, N - k, N - 1);//整体逆置fun(nums, 0, N - 1);int i = 0;for (i = 0; i < numsSize; i++){printf("%d ", nums[i]);}
}

方法三：

#include<stdio.h>
#include<stdlib.h>
void rotate(int* nums, int numsSize, int k) {int* pf=(int*)malloc(numsSize*sizeof(int));if(pf==NULL){perror("malloc");}k=k%numsSize;int i=0;int j=0;for(i=numsSize-k;i<numsSize;i++)//i取4到6{pf[j]=nums[i];j++;}for(i=0;i<numsSize-k;i++)//i取0到3{pf[j]=nums[i];j++;}for(i=0;i<numsSize;i++){nums[i]=pf[i];}
}

练习二移除元素OJ链接：. - 力扣（LeetCode）

int removeElement(int* nums, int numsSize, int val) {int i = 0;int j = 0;for (i = 0; i < numsSize; i++) {if (nums[i] == val){continue;}nums[j] = nums[i];j++;}return j;
}