1、复杂度总结
1、时间复杂度计算遵循的原则
1、复杂度与其具体的常系数无关（即：常数项的系数不要）
2、多项式级复杂度相加的时候，把其高项作为结果（即：多项式只保留最大项）
3、O(1)含义为：某个任务通过有限可数的资源即可完成
注：有限可数与输入的数据量n无关——常量复杂度
2、关于复杂度的经验性结论
1、一个顺序结构的代码，时间复杂度为O(1)——单纯的顺序或选择
2、采用分治法的二分策略，时间复杂度为O(log2 n) //log以2为底n的对数
3、一个简单的for循环，时间复杂度为O(n)
4、两个顺序执行的for循环，时间复杂度是取高项——并列的不累加
5、一般情况下，两层嵌套的for循环，时间复杂度为O(n²)
6、一般情况下，会使用递归，分治，动态规划等方法，用空间换取时间效率——时间宝贵、空间廉价
时间复杂度与代码结构有关，空间复杂度与数据结构有关
2、数据结构
数据结构分为线性结构和非线性结构，线性结构分为顺序存储和链式存储
线性结构：数组、链表、队列、栈、字符串
非线性结构：集合、树、图
数组和链表区别：
数组：空间连续、类型相同、长度固定的集合（顺序存储）
链表：增删快，但付出了查找的代价（链式存储）
| 数组 | 链表 | |||
| 是否连续 | 一定 | 不一定 | ||
| 大小 | 固定 | 不固定 | ||
| 查找 | 按照索引 | O(1) | O(n) | |
| 按照数值 | 有序 | 采用二分搜索 | ||
| 无序 | O(n) | |||
| 插入删除 | 头部 | O(n) | O(1) | |
| 中间 | O(n) | O(n) | ||
| 尾部 | O(1) | O(n) | ||
例题
存在一个含有n个元素的数组，数组内元素值均为0——n-1，检测数组内是否含有相同重复元素
解法
| 解法 | 时间复杂度 | 空间复杂度 |
| 1、暴力 | O(n**2) | O(1) |
| 2、容器 | O(n) | O(n) |
| 3、额外申请一个计数数组 | ||
| 4、排序后查看相邻数组元素值 | O(n*logn) | O(log2n) |
| 5、检测是否有没有出现的元素 | O(n**2) | O(1) |
| 6、sort+二分 | 更高 | O(n) |
| 7、在数组内部，将元素下标与元素值一一对应 | O(n) | O(1) |
1、按顺序把数组内每一个元素取出来，与后面每一个元素进行比较，如果有重复则报错
2、申请一个与原数组个数相同的数组，里面保存出现次数（2、3）
6、申请一个与原数组相同的数组，先将第一个元素放入数组内，接下来使用二分搜索法查找每个元素是否存在数组内
第七种方法代码
#include<iostream>bool check(int arr[],int length)
{int index = 0;for (int i = 0; i < length; i++){if (arr[index] == index){index++;}else{if (arr[arr[index]] == arr[index]){return false;}else{int t = arr[arr[index]];arr[arr[index]] = arr[index];arr[index] = t;}}}return true;
}int main()
{int arr[9] = { 1,2,8,4,3,5,0,7,6 };int length = sizeof(arr)/sizeof(int);if (check(arr, length)){printf("没有重复元素");}else{printf("有重复元素");}return 0;
}
