数据结构算法时间复杂度定义,数据结构与算法,请问时间复杂度是怎么判定的?

2021-01-05 12:04:38 字数 4888 阅读 1789

1楼:匿名用户

1)时间频度

一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。

一个算法中的语句执行次数称为语句频度或时间频度。记为t(n)。

2)时间复杂度

在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时间频度t(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,我们引入时间复杂度概念。

一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用t(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,t(n)/f(n)的极限值为不等于零的常数,则称f(n)是t(n)的同数量级函数。记作t(n)=o(f(n)),称o(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。

在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为o(1),另外,在时间频度不相同时,时间复杂度有可能相同,如t(n)=n^2+3n+4与t(n)=4n^2+2n+1它们的频度不同,但时间复杂度相同,都为o(n^2)。

按数量级递增排列,常见的时间复杂度有:

常数阶o(1),对数阶o(log(2)n),线性阶o(n),

线性对数阶o(nlog(2)n),平方阶o(n^2),立方阶o(n^3),...,

k次方阶o(n^k),指数阶o(2^n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。

数据结构与算法,请问时间复杂度是怎么判定的?

2楼:匿名用户

显然是c

外层k增长速度了 *2 意味着 跑完n个数 只需要logn次,内层n 是线性增长, 时间复杂度是n

乘一起就是 o(nlogn)

复杂度就是几种,线性的 n, 多项式的 n^k 幂指数 k^n , logn, 其中n的系数是多少都无关紧要,时间复杂度的基础就是n的增长速度,2n也是n ; (2n)^2 也是n^2

3楼:月光星屑

计算时间复杂度的时候一般把 加 和 乘 的系数去掉,比如:o(0.5*n^2+n+0.5)记为o(n^2)

4楼:匿名用户

算法是处理数据的一种方法,最终也是为了解决某一个或某一类问题,而通常情况下,问题的解决思路都不只一种!所以看情况而定!

数据结构中算法的时间复杂度怎么理解?

5楼:匿名用户

就是基本操作语句执行的次

数如果你能确定基本执行语句,那就可以假设需要执行的次数是n,然后根据程序的控制部分得到关于n的一个函数,就可以求的了。

如int int=3;

do{i*=3;

)while(i<100);

那么我们可以这样立即,就是i*=3是基本语句,do~while是控制结构,在控制结构下,要保证

i*=3执行n此后,能使得最后i<100退出控制结构。

那么你去算吧,对于i来说,每次都是乘以3,那执行n次,就相当于乘了n个3,然后满足了<100、因此可以组成一个函数 就是3的n次方<100那你解方程来求n

就得了。

不过时间复杂度用渐进函数表示的。

6楼:匿名用户

比如数据规模n,时间复杂度就是运行开始到结束大概需要循环的平均次数 跟n的关系

数据结构中算法的时间复杂度是什么?

7楼:曹妃贲溪

程序所用时间关于数据规模的函数

比如:给n个数排序需要n^2的时间

时间复杂度专就是o(n^2)

通常属有

o(2)

常数与输入数据规模无关

o(n)

成正比o(log2n)

平方与数据规模成正比

o(n^2)

与数据规模的平方成正比

o(n^3)

……三次方……

o(n!)阶乘

数据结构算法的时间复杂度

8楼:匿名用户

按照分析惯例,假设所有单一运算的时间复杂度均为1

x=n; ......1

while(x>=(y+1)*(y+1)) ......4(两次加法、1次乘法、1次比较)

y=y+1 ......1

时间复杂度 = 1 + (4 + 1) x 循环次数

循环次数是由n和y的初始值决定的,假设循环次数为n,y的初始值为y0,y的结束状态为yn,有

x < (yn + 1)*(yn + 1) ......假设y的初始值为整数,则yn为满足该式的最小整数

n = (yn - y0) / 1 ......因为每次循环y的递增量为1

1式简化为 x = (yn + 1)*(yn + 1),可得:yn = n^(1/2) - 1

所以n = n^(1/2) - 1 - y0

采用大o表示法,仅考虑最高次项,则求n的复杂度为o(n^(1/2))

进而求得你这3行**的

总体复杂度 = 1 + (4 + 1) x o(n^(1/2))

由于已知的常数项及非最高次项通常会被忽略(大o精神),所以总时间复杂度为o(n^(1/2))

9楼:匿名用户

************我谈**********************

“如果执行时间的算法不按照问题规模n的增加而增长,即使成千上万的语句的算法,其执行的时间,但也有大量的常数。该算法的时间复杂度是o(1)。“

不要明白这一点吗?

所以该算法是不是说多少单一的语言

温度=;

= j;

j =温度; />共三种语言中,和每个频率是1,且每个频率可以被认为是o(1),则t(n)的= o的(1)+ o(1)+ o(1)= o( 1)。

以下四个语句:

scanf的(“为%d”,&n);

= n;

(i = 0,

(i = 0,i

前两个栏的频率分别为

频率为n和n * n

(1)的总频率的所有

o. + o (1)+ o(n)+ o(n * n)= o(n * n)

(为什么这个等式的左边是等于右侧的o(n * n)??不要问我,我懒得说了,这是一个c / c + +的问题,这是一个数学问题,不明白自己看到的高等数学。)

声明,更多的是总是有限的,或一个单独的语句的频率最花时间

单个语句,比如for()}}而( 1)}等等这样的,可以视为一个忘记

一份声明中可以执行了n年没有完成,如:f(i = 0; + +),除非你终止!!

10楼:

n^(1/2)-y0=o(n^(1/2))

数据结构算时间复杂度

11楼:匿名用户

简单理解,时间复杂度就是执行语句被调用了多少次。 (1)如果只调用了一次,如: x=5; if(x<-4) else 在大括版号中的内容权

,只会调用一个语句,那么o(n)=1; (2)如果调用了两次,如: x=5; if(x<-4) else x=x+56; 在大括号中的内容,只会调用一个语句,但是在最后,还有一个计算公式要调用语句;总共加起来就是调用2次。那么o(n)=2; (3)用1个for循环调用 for(x=0;x

数据结构算法(并说明时间复杂度和空间复杂度)

12楼:匿名用户

算法主要用了一个bai额外du的先入后出的线性表(即栈zhi),假定dao数组为版num[n],流程如下:

1.先申请一个能存放权n个整数的栈。

2.把原有数组的后n-p个元素,从后面num[n-1]到num[p]开始依次压入栈。

3.把数组的前p个元素,从num[p-1]开始,把num[n-1]=num[p-1],依次类推,直到

num[n-p]=num[0].

4.把栈中的数弹出,依次放入数组num[0]、num[1]····中,直到放完。

5,这样所得的结果就是所需要的结果。

时间复杂度o(n),空间复杂度也是o(n).

c语言,数据结构中 算法的时间复杂度

13楼:匿名用户

有个很难的算法,不知道楼上楼下的大虾们能不能算出,for(int i=0;i

for(int j=0;j

a[i][j]=i*j;谁能算出并能讲出,我就f他

14楼:匿名用户

把那些抄基本的时间复杂度记住,然后袭遇到循环就bai

相乘,遇到顺序du结构就相加,而一般zhi

高阶的复杂度可以吞dao并低阶的。比如说,二分法的复杂度是和log(n)同阶,如果再出现在对n个数的遍历的循环中,复杂度就是和n*log(n)同阶。如果先二分查找,再顺序查找,就是n+log(n)。

15楼:匿名用户

了解c 语言程序设计中的 复杂度,建议咨询一下龙腾it教育

数据结构与算法 算法的时间复杂度是怎么求的

16楼:匿名用户

就是求一个多项式,比如for(i=0;i数是n次,那么这个复杂度就内是o(n)

for(i=0;i容是n^2所以复杂度是o(n^2)

数据结构中各种排序的时间复杂度与空间复杂度比较

1楼 匿名用户 冒泡排序 是稳定的,算法时间复杂度是o n 2 。 2 2 选择排序 selection sort 选择排序的基本思想是对待排序的记录序列进行n 1遍的处理,第i遍处理是将l i n 中最小者与l i 交换位置。这样,经过i遍处理之后,前i个记录的位置已经是正确的了。 选择排序是不稳...

如何对程序进行算法分析?时间复杂度怎么算

1楼 匿名用户 算法的复杂性 算法的复杂性是算法效率的度量,是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面,所需的资源越多,我们就说该算法的复杂性越高 反之,所需的资源越低,则该算法的复杂性越低。 计算机的资源,最重要的是时间和空间 即存储器 资源。因而...

归并排序的时间复杂度是多少,归并排序的时间复杂度O是怎么算出来的呢

1楼 二分归并排序是一种分治算法 主定理方法 符合主定理 case 2 动动你的小手点个赞。 2楼 伟大的小天同学 o nlogn 和o nlog2n 是一样的。。归并排序如果不借助辅助空间的话,复杂度为o n 2 ,借助的话就是o nlogn o nlog2n 3楼 o n 以2为底的n的对数 。...