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

算法开章咯

这次是csp-j组算法

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

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

时间复杂度

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

        1，O(1)代码

s=a*b;
cout<<s;

        2，O(n)代码

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

        3,O(log^{2}(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^{2}(n))

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

         5，O(n^{2})

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

空间复杂度

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

本章节结束！！！