1000字范文,内容丰富有趣,学习的好帮手!
1000字范文 > 时间和空间复杂度的计算方法

时间和空间复杂度的计算方法

时间:2020-02-03 20:55:22

相关推荐

时间和空间复杂度的计算方法

时间复杂度与空间复杂度都是针对算法而言的,我们知道数据+算法=程序,那么一个程序在运行过程中,必然要占用计算机的内存资源,而计算结果也需要时间;

那么我们可以这样理解:

时间复杂度 = 程序运行的时间;

空间复杂度 = 程序占用的内存;

但是对于运行时占用的时间,根据运行环境的不同,其结果也是不同的,所以在数学上,使用一个公式来表示:大O符号表示法即 T(n) = O(f(n))

时间复杂度:

对于没有循环结构的普通算法:T(n) = O(1)

对于有循环结构的算法:T(n) = O(n)

for(i=1; i<=n; ++i){j = i;j++;}

对于有循环嵌套结构的算法:T(n) = O(n^2)

for(x=1; i<=n; x++){for(i=1; i<=n; i++){j = i;j++;}}

以此类推:T(n) = O(n^3),T(n) = O(n^4) .......T(n) = O(n^n)

对于循环中有乘法的算法:T(n) = O(logn)

int i = 1;while(i<n){i = i * 2;}

组合一下:T(n) = O(nlogn)

for(m=1; m<n; m++){i = 1;while(i<n){i = i * 2;}}

其他以此类推;

空间复杂度:S(n) = O(f(n))

空间复杂度主要针对的是变量:

int i = 1;S(n) = O(1)

int[] a = new int[n];S(n) = O(n)

int[] a = new int[n][n];S(n) = O(n^2)

其他以此类推;

本内容不代表本网观点和政治立场,如有侵犯你的权益请联系我们处理。
网友评论
网友评论仅供其表达个人看法,并不表明网站立场。