如何计算算法的复杂度
时间复杂度
什么叫做时间复杂度呢？？
我们来看一个简单的程序
int n = 10 ;
System.out.println("输出" + n);这段伪代码运行了多少次呢！ 1次 ，时间时间复杂度为O(1)：常数复杂度/常数阶。
for (int i = 0 ;i <n; i++){
System.out.println("第几次"+i);
}这个for循环了多少次呢！ n次，时间复杂度为O(n)：线性时间复杂度。
再看下一个
for (int i = 0 ;i <n; i++){
for (int j = 0 ;j < n; j ++) {
System.out.println("第几次" + i+""+j);
}
}这个循环了多少次呢！n*n次，时间复杂度为O(
n^2
)：平方复杂度。
百度百科对时间复杂度的定义是：在计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。
我们再把常见的复杂度列举出来看看。
int j = 0;
for (int i = 0 ; i < n ; i++) {
i = i * 2;
j++;
System.out.println("第几次"+j);
}这个循环了多少次呢！假设我们把次数设为x，那
2^x<n
，解得次数
x=log(n)
，时间复杂度为O(log(n))：对数。
for (int i = 0 ; i < Math.pow(2,n); i++) {
System.out.println("第几次"+i);
}这个循环了多少次呢！
2^n
次，时间复杂度为O(
2^n
)：指数复杂度。
空间复杂度
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。
简单的讲就是包括下面几部分。
1.存储算法本身所占用的存储空间。
2.算法的输入输出数据所占用的存储空间。
3.算法在运算过程中临时占用的存储空间这三个方面。
int a[] = new int[n];这个例子的空间复杂度是多少呢？这个数组开辟的空间是多少呢？ O(n)。
总结
时间复杂度和空间复杂度本就是一个相互博弈的过程，一个多另一个就少，根据适当的问题，找到适当的解，这才是好办法。
下面给一张常见数据结构时间和空间复杂度的图作为结尾把。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-07-16 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录