算法的时间复杂度是指什么

算法的时间复杂度是指用来方便开发者估算出程序的运行时间。

我们该如何估计程序运行时间呢，我们通常会估计算法的 *** 作单元数量，来代表程序消耗的时间， 这里我们默认CPU的每个单元运行消耗的时间都是相同的。

假设算法的问题规模为n，那么 *** 作单元数量便用函数f(n)来表示。随着数据规模n的增大，算法执行时间的增长率和f(n)的增长率相同，这称作为算法的渐近时间复杂度，简称时间复杂度，记为 O(f(n))。

在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同。

算法的复杂性

算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。

计算机的资源，最重要的是时间和空间（即存储器）资源。因而，算法的复杂性有时间复杂性和空间复杂性之分。

不言而喻，对于任意给定的问题，设计出复杂性尽可能低的算法是我们在设计算法时追求的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是我们在选用算法适应遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。

简言之，在算法学习过程中，我们必须首先学会对算法的分析，以确定或判断算法的优劣。

1时间复杂性：

例1：设一程序段如下（为讨论方便，每行前加一行号）

(1) for i:=1 to n do

(2) for j:=1 to n do

(3) x:=x+1

试问在程序运行中各步执行的次数各为多少？

解答：

行号 次数(频度)

(1) n+1

(2) n(n+1)

(3) nn

可见，这段程序总的执行次数是：f(n)=2n2+2n+1。在这里，n可以表示问题的规模，当n趋向无穷大时，如果 f(n)的值很小，则算法优。作为初学者，我们可以用f(n)的数量级O来粗略地判断算法的时间复杂性，如上例中的时间复杂性可粗略地表示为T(n)=O(n2)。

2空间复杂性:

例2:将一一维数组的数据(n个)逆序存放到原数组中,下面是实现该问题的两种算法:

算法1:for i:=1 to n do

b[i]:=a[n-i+1];

for i:=1 to n do

a[i]:=b[i];

算法2:for i:=1 to n div 2 do

begin

t:=a[i];a[i]:=a[n-i-1];a[n-i-1]:=t

end;

算法1的时间复杂度为2n,空间复杂度为2n

算法2的时间复杂度为3n/2,空间复杂度为n+1

显然算法2比算法1优，这两种算法的空间复杂度可粗略地表示为S(n)=O(n)

信息学比赛中，经常是：只要不超过内存，尽可能用空间换时间。

时间复杂度为O(n^05)，即根号n的数量级。该程序求解的是：s=1+3+5+7++(2k+1)，且使得s-(2k+1)<n≤s。而s=(1+(2k+1))(k+1)/2=(k+1)^2，k+1则为上述等差数列的项数，也是你的程序中while循环执行的趟数。求出k<根号n≤(k+1)，因此循环执行根号n趟。则T(n)=2+5n^05+1，解释一下T(n)这个式子，第一项2表示最开始的2个赋值 *** 作；第二项中n^05表示循环的趟数，前面的系数5表示每趟有5个基本 *** 作：一次循环条件判断、两次加法、两次赋值；第三项的1表示最后的一次循环条件判断（因不满足条件但没执行该趟循环）。所以T(n)=5n^05+3，所以O(T(n)=O(5n^05+3)=O(n^05)。

以上就是关于算法的时间复杂度是指什么全部的内容，包括:算法的时间复杂度是指什么、在一个具体的程序中，程序的复杂度是如何计算的、程序时间复杂度计算 i=-1; s=0; while(s<n) { i=i+等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！