c++算法——算法章节-时间空间复杂度

算法开章咯

这次是csp-j组算法

1. 枚举法
2. 常用排序合集
3. hash
4. 一维前缀和
5. vector
6. 结构体
7. queue
8. stack
9. 贪心-简单
10. 贪心区间
11. 递归
12. 二分
13. set
14. map
15. 二叉树
16. 图的遍历-邻接矩阵
17. 迷宫问题-dfs-深度优先搜素
18. bfs-广度优先搜索
19. 动态规划-简单
20. 动态规划-01背包
21. 动态规划-背包-多重背包
22. 二分答案

算法是什么嘛，懒得介绍了，自己看！

时间复杂度

 时间复杂度就是用来方便人估算出程序的运行时间所创的，一般程序如果运行超过1亿次就大概超时了，比如枚举法，枚举经常需要通过很多循环来得到答案，举个例子枚举用了两重 for 循环每一层循环10万次，10万乘10万等于100亿，这就超了很多，如果还是用了两重循环，每重循环 n 次，时间复杂度就是O()。

        1，O(1)代码

s=a*b;
cout<<s;

        2，O(n)代码

for(int i=0;i<=n;i++){cout<<i<<" ";
}

        3,O(log(n))代码

int bin(int left,int right,int key){//二分while(left<=right){int mid=(right+left)/2;if(key==a[mid]){return mid; } if(key>a[mid]){left=mid+1;}if(key<a[mid]){right=mid-1;}}return -1;
}

​​​        4，O(n*log(n))

sort(a,a+n);//快排

         5，O()

for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout<<"点赞，收藏"<<" ";}
} 

空间复杂度

一般是256M，超不了，哈希就是用空间换时间。

本章节结束！！！