复习下时间复杂度计算
http://blog.csdn.net/zhuchzhi/archive/2007/03/14/1529514.aspx
http://blog.csdn.net/iluna/archive/2009/05/09/4159485.aspx
按数量级递增排列依次为:常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。
有如下复杂度关系
c < log2N < n < n * Log2N < n^2 < n^3 < 2^n < 3^n < n!
sum=0; (一次)
for(i=1;i<=n;i++) (n次 )
for(j=1;j<=n;j++) (n^2次 )
sum++; (n^2次 )
解:T(n)=2n^2+n+1 =O(n^2)
i=1; ①
while (i<=n)
i=i*2; ②
解:语句1的频度是1, 设语句2的频度是f(n), 则:2^f(n)<=n;f(n)<=log2n
取最大值f(n)= log2n,则该程序的时间复杂度T(n)=O(log2n )
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
for(k=0;k<j;k++)
x=x+2;
}
}
解:当i=m, j=k的时候,内层循环的次数为k
当i=m时, j 可以取 0,1,...,m-1 , 所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次
所以,i从0取到n, 则循环共进行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6
所以时间复杂度为O(n^3).
分享到:
相关推荐
算法复杂度分析算法复杂度分析算法复杂度分析算法复杂度分析算法复杂度分析算法复杂度分析
均值滤波很常见 但一般的算法复杂度都和取值窗口w*h有关 算法复杂度太高 本算法优化了基础的均值滤波算法 算法复杂度大大降低
算法复杂度计算方法
程序员应该掌握的算法复杂度速查表 这个总结非常方便 不仅形象地把各个算法对比开来 也特别利于面试前的复习。
这是讲解算法复杂度的概念的PPT。希望大家能有所收获。
这是数据结构算法课程中算复杂度的作业及答案。
从原理上理解算法复杂度的概念与本质,并不是一搜就搜到的描述,适合初学者学习。
包含算法复杂度分析的基本知识,包含时间复杂度和空间复杂度分析的基本思路
降低PTS算法复杂度的新方法.pdf 降低PTS算法复杂度的新方法.pdf
算法复杂度——时间复杂度和空间复杂度.doc
用matlab实现dft和fft算法复杂度比较
c/c++阵连乘,编译不错,挺好的!大家可以过来试试。还有源代码和题目描述和算法复杂度的解析。
排序算法复杂度总结
数据结构与算法复杂度速查表是一款对常用数据结构与算法的复杂程度进行快速查询的表格。 数据结构与算法复杂度速查表演示图:
最大公约数的三种算法复杂度分析时间计算.doc
这是博客《由数据范围反推算法复杂度以及算法内容》的配套资源word文档 博客网址:https://blog.csdn.net/wyuchen123/article/details/136720139
算法设计技巧与分析第1章算法基本概念之算法复杂度概要.ppt
一个算法的复杂度如何判断,各种排序算法的复杂度解析。
常用排序算法时间复杂度、空间复杂度总结。包括:冒泡排序、快速排序、选择排序、堆排序、插入排序、Shell排序、归并排序、基数排序。
快速幂 基于java实现的快速幂、快速乘算法,利用二进制位运算将O(n)的算法复杂度降到O(logn)