定义:如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数 T(n)称为这一算法的“时间复杂性”。
当输入量n逐渐加大时,时间复杂性的极限情形称为算法的“渐近时间复杂性”。
我们常用大O表示法表示时间复杂性,注意它是某一个算法的时间复杂性。大O表示只是说有上界,由定义如果f(n)=O(n),那显然成立f(n)=O(n^2),它给你一个上界,但并不是上确界,但人们在表示的时候一般都习惯表示前者。
此外,一个问题本身也有它的复杂性,如果某个算法的复杂性到达了这个问题复杂性的下界,那就称这样的算法是最佳算法。
“ 大O记法”:在这种描述中使用的基本参数是 n,即问题实例的规模,把复杂性或运行时间表达为n的函数。这里的“O”表示量级 (order),比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时,运行时间至多将以正比于 f(n)的速度增长。
这种渐进估计对算法的理论分析和大致比较是非常有价值的,但在实践中细节也可能造成差异。例如,一个低附加代价的O(n2)算法在n较小的情况下可能比一个高附加代价的 O(nlogn)算法运行得更快。当然,随着n足够大以后,具有较慢上升函数的算法必然工作得更快。
O(1)
Temp=i;i=j;j=temp;
以 上三条单个语句的频度均为1,该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶,记作T(n)=O(1)。如果算法的执行时 间不随着问题规模n的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
O(n^2)
2.1. 交换i和j的内容
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)
2.2.
for (i=1;i<n;i++)
{
y=y+1; ①
for (j=0;j<=(2*n);j++)
x++; ②
}
解: 语句1的频度是n-1
语句2的频度是(n-1)*(2n+1)=2n^2-n-1
f(n)=2n^2-n-1+(n-1)=2n^2-2
该程序的时间复杂度T(n)=O(n^2).
O(n)
2.3.
a=0;
b=1; ①
for (i=1;i<=n;i++) ②
{
s=a+b; ③
b=a; ④
a=s; ⑤
}
解: 语句1的频度:2,
语句2的频度: n,
语句3的频度: n-1,
语句4的频度:n-1,
语句5的频度:n-1,
T(n)=2+n+3(n-1)=4n-1=O(n).
O(log2n )
2.4.
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 )
O(n^3)
2.5.
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).
我 们还应该区分算法的最坏情况的行为和期望行为。如快速排序的最 坏情况运行时间是 O(n^2),但期望时间是 O(nlogn)。通过每次都仔细 地选择基准值,我们有可能把平方情况 (即O(n^2)情况)的概率减小到几乎等于 0。在实际中,精心实现的快速排序一般都能以 (O(nlogn)时间运行。
下面是一些常用的记法:
访问数组中的元素是常数时间操作,或说O(1)操作。一个算 法如 果能在每个步骤去掉一半数据元素,如二分检索,通常它就取 O(logn)时间。用strcmp比较两个具有n个字符的串需要O(n)时间 。常规的矩阵乘算法是O(n^3),因为算出每个元素都需要将n对 元素相乘并加到一起,所有元素的个数是n^2。
指数时间算法通常来源于需 要求出所有可能结果。例如,n个元 素的集合共有2n个子集,所以要求出所有子集的算法将是O(2n)的 。指数算法一般说来是太复杂了,除非n的值非常小,因为,在 这个问题中增加一个元素就导致运行时间加倍。不幸的是,确实有许多问题 (如著名 的“巡回售货员问题” ),到目前为止找到的算法都是指数的。如果我们真的遇到这种情况, 通常应该用寻找近似最佳结果的算法替代之。
本文来源:http://blog.csdn.net/comicray/archive/2009/08/22/4472580.aspx
分享到:
相关推荐
#### 一、算法复杂度概述 在计算机科学领域,算法的时间复杂度与空间复杂度是衡量一个算法效率的重要指标。时间复杂度关注的是算法执行时间的增长速率,而空间复杂度则侧重于算法运行过程中所需内存空间的大小。 #...
### 算法复杂度计算方法 #### 一、时间复杂度 时间复杂度是用来评估算法执行速度的一个重要指标,通常用于衡量算法随输入数据规模(通常标记为n)的增长趋势。 ##### 1. 时间频度 - **定义**:算法执行过程中基本...
在计算机科学领域,算法的时间复杂度是对算法运行所需计算工作量的度量,它反映了算法执行效率与输入数据规模之间的关系。本实验测试的主题聚焦于堆排序算法的时间复杂度分析,由胡书晗进行研究。堆排序是一种基于...
了解和掌握分治法及其时间复杂度计算,能帮助我们设计出更高效的算法,解决大规模数据处理问题。通过阅读《分治法与时间复杂度计算.pdf》这份文档,你将深入理解这些概念,并能够运用到实际编程中去。
时间复杂度讨论的通常是算法在最坏情况下的表现,这是因为最坏情况的时间复杂度确保了算法在任何输入实例下都不会运行得更慢。在实际计算过程中,有时会忽略求解极限的过程,因为当 n 趋于无穷大时,1/n 会趋近于 0...
### 算法时间复杂度分析中递归方程求解方法综述 #### 引言 在计算机科学领域,递归是一种常见的编程思想和技术,它不仅被广泛应用于各种算法的设计之中,也是评估算法效率的重要工具之一。递归方程在算法的时间...
算法复杂度分为时间复杂度和空间复杂度。 其作用: 时间复杂度是指执行算法所需要的计算工作量; 而空间复杂度是指执行这个算法所需要的内存空间。 (算法的复杂性体现在运行该算法时的计算机所需资源的多少上,...
在"数据结构和算法-1-算法的引入和算法时间复杂度.pdf"文件中,你可能会学习到如何定义和表示算法,如何分析和比较不同算法的时间复杂度,以及如何通过实例来理解和应用这些概念。通过深入学习这部分内容,你可以...
通过本文的介绍,我们学习了时间复杂度的基本概念、影响因素、分析方法,并结合数据结构和具体算法实例进行了分析。掌握这些知识可以帮助开发者设计出更高效的算法,优化程序性能。 本文详细介绍了时间复杂度分析的...
算法复杂度是衡量一个算法效率的重要指标,它主要关注在最坏、最好和平均情况下,算法执行时间或空间需求的增长趋势。理解算法复杂度对于优化程序性能和选择合适的算法至关重要。初学者在学习这一概念时,应从以下几...
2. **在修改后的运行次数函数中,只保留最高阶项**:这一步是为了确定算法复杂度的主要贡献项。 3. **如果最高阶项存在且不是1,则去除与这个项相乘的常数**:这样可以得到算法时间复杂度的基本形式。 #### 三、...
在这个实例中,算法的执行时间是T(n)=2n^2+2n+2,故时间复杂度是O(n^2),也就是说执行时间与问题规模n的平方成正比。 例四:i=1;while (i)i=i*2; 在这个实例中,算法的执行时间是2log2n+2 (n) ,故时间复杂度是O...
《算法与数据结构》笔记—算法及时间复杂度 在计算机科学领域中,算法是解决问题的步骤序列。...在实际问题中,时间复杂度的计算非常重要,我们需要考虑输入规模和时间复杂度的关系来选择合适的算法。
接着,文章提供了排序算法、搜索算法、图算法和字符串算法等具体算法的时间复杂度实例,并讲解了时间复杂度的计算方法,最后强调了时间复杂度在评估算法效率、优化算法和预测性能方面的重要作用。 适合人群:计算机...
本文将深入探讨时间复杂度和渐进时间复杂度的概念,并通过实例解析如何计算和分析算法的时间复杂度。 首先,时间复杂度是算法执行所需的基本操作次数,通常用大O记法表示。大O记法是一种表示算法运行时间上限的符号...
时间复杂度的数学意义是指给定算法 A,如果存在函数 F(n),当 n=k 时,F(k) 表示算法 A 在输入规模为 k 的情况下的运行时间,则称 F(n) 为算法 A 的时间复杂度。 输入规模是指算法 A 所接受输入的自然独立体的大小...
本文将深入探讨数据结构、算法的总结,以及学习算法时应关注的时间复杂度和空间复杂度。 首先,数据结构是组织、管理、存储和检索数据的方式。常见的数据结构有数组、链表、栈、队列、哈希表、树(如二叉树、平衡树...
在计算机科学中,算法的效率通常通过时间和空间复杂度来衡量。时间复杂度关注算法执行所需的时间,而空间复杂度则关注算法执行过程中所需的存储空间。理想情况下,我们希望算法既快速又节省空间,但在实际应用中,...