数据结构----算法复杂度分析
2021/4/15 20:55:15
本文主要是介绍数据结构----算法复杂度分析,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
- 时间复杂度
- 常数阶
int i = 0;int n = 100; printf("test"); printf("test"); printf("test"); printf("test"); //算法时间复杂度为O(1)
2、线性阶 O(n):随着问题规模n的增大,对应的计算次数成直线增长
int i = 0;int n = 100; int sum = 0; for(i=0; i<n; i++) { sum = sum + i; } //算法时间复杂度为O(n)
3、平方阶 O(n^2):随着问题规模n的增大,对应的计算次数成抛物线增长
int i = 0, j = 0;int n = 100; int sum = 0; for(i=0; i<n; i++) { for(j=0; j<n; j++) { printf("ok"); } } //算法时间复杂度为O(n^2) for(i=0; i<n; i++) { for(j=i; j<n; j++) { printf("ok"); } }//n + n-1 + n-2 + ... + 1 = n*(n+1)/2 ---> O(n^2) //算法时间复杂度为O(n^2)
4、对数阶 O(log(n)):随着问题规模n的增大,对应的计算次数成对数线增长
int i = 1; int n = 100; while(i < n) { i = i * 2; }//2^x = n --->x = log(n) //算法时间复杂度为O(log(n))
5、总结 常用时间复杂度耗费时间从小到大排列: O(1) < O(log(n)) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
- 空间复杂度
这篇关于数据结构----算法复杂度分析的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-29DataGrip使用ssh连接数据库的操作流程
- 2024-05-28SpringBoot3.2更新声明!
- 2024-05-28中外程序员到底有啥区别?
- 2024-05-25外企也半夜发布上线吗?
- 2024-05-24鸿蒙原生应用再新丁!芒果TV 入局鸿蒙
- 2024-05-22基本概念
- 2024-05-22检索数据
- 2024-05-22排序数据
- 2024-05-22基础过滤数据
- 2024-05-22通过逻辑操作符过滤数据