数据结构与算法——1122—复杂度总结检测相同元素

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