从一些简单的例子看算法时间复杂度

简介: 从一些简单的例子看算法时间复杂度

在编程中,一段代码的执行效率实际上很难估算和预测,其主要受到如下几个方面的影响:

1.算法依据的数学基础。

2.编译器产生的代码质量和语言的执行效率。

3.问题的输入规模。

4.硬件的执行速度。

通常情况下,问题的输入规模和算法的数学基础是编码人员需要考虑的条件。时间复杂度是一个用来描述算法执行效率的重要标准。

在理解时间复杂度之前,你应该先了解什么叫做算法的时间频度,所谓时间频度即是一个算法解决问题所消耗的时间。但是一般情况下,一个算法解决问题消耗的时间通常与输入值有关,例如我们输入一个整数,找到比它小的所有正偶数,代码如下:

let n = 10;

for (var i = 0; i < n; i++) {

if (i%2==0) {
    console.log(i);
}

}
上面代码,当输入n为10时,循环会执行10次,如果时间频度t,则当输入n为20时,时间频度为2t。时间复杂度是用来描述随着问题规模n的变化时间频度t的变化规律。下面是一段更加数学风格的描述:

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

计算一个算法的时间复杂度时,我们可以将算法分解为逐条语句,计算每条语句的时间复杂度后再进行累加,如下代码的作用是对输入进行求累加:

let n = 10;
let res = 0; //1
for (var i = n; i > 0; i--) { //1+(n+1)+(n+1)

res = i+res;  //n

}
console.log(res);//1
当n输入为10时,时间频度为1+1+n+1+n+1+n+1 = 3n+5。设算法的时间复杂度函数为f(n),(3n+5)/f(n)当n趋于无穷大时,上式可以简化为3n/f(n),取f(n)=n,上次结果为非零常数,因此此算法的时间复杂度为f(n)=n,记做O(n)。

当算法的执行时间频度和n无关时,算法的时间复杂度为O(1),这是时间复杂度最小的函数,但是需要注意,时间复杂度小并不能说明算法执行耗费的时间短,比如一万行代码每行只执行一次的算法时间复杂度也为O(1)。

 常见的算法时间复杂度由小到大以此为:

Ο(1)<Ο(log²n)<Ο(n)<Ο(nlog²n)<Ο(n2)<Ο(n3)<…<Ο(2n)<Ο(n!)

其中O(log² n)是除了O(1)外时间复杂度最小的函数,例如如下代码:

let n = 10;
var i = 1;

while(i<n){//2^t<n t<log2(n) t为时间频度

i = i * 2;
tip++;

}
上面的时间频度为 1+1+log2(n)+log2(n)+log2(n),去掉常数项后为3log2(n),时间复杂度为O(log2(n))。如果将上面的代码在加一层循环,则时间复杂度会变为O(nlog3(n)):

let n = 10;

for (var i = 0; i < n; i++) {// 1+n+1+n+1

var j = 1;   //n
while(j<n){//[3^t<n t<log3(n)]n  t为时间频度
    j = j*3;
}

}

通过上面的示例,也很容易可以看出,循环层数的增多会剧烈的增加算法的时间复杂度,如果在递归函数中使用循环,则很容易产生时间复杂度为O(n!)的代码,从数学上看,这种代码随着输入复杂度的增加性能会急剧下降,在使用递归加循环时,还是要多多注意,示例代码如下:

function func(n) { //n

if (n<0) {
    return;
}
var i = 0;    //n
for (; i < n; i++) { //n*(n-1)*(n-2)...*1
    console.log("tip");
}
func(--i);

}
func(10);
上面示例的JavaScript代码当传入n为150时的耗时已经和正常循环10000次的相同。

目录
相关文章
|
12月前
|
机器学习/深度学习 缓存 算法
Python算法设计中的时间复杂度与空间复杂度,你真的理解对了吗?
【10月更文挑战第4天】在Python编程中,算法的设计与优化至关重要,尤其在数据处理、科学计算及机器学习领域。本文探讨了评估算法性能的核心指标——时间复杂度和空间复杂度。通过详细解释两者的概念,并提供快速排序和字符串反转的示例代码,帮助读者深入理解这些概念。同时,文章还讨论了如何在实际应用中平衡时间和空间复杂度,以实现最优性能。
205 6
|
机器学习/深度学习 算法 程序员
读《趣学算法》:重开算法之门,时间复杂度与空间复杂度
本文是作者阅读《趣学算法》后的笔记,介绍了算法复杂度的基本概念,包括时间复杂度和空间复杂度的不同阶表示,并通过具体例子展示了如何计算和理解算法的效率。
155 2
读《趣学算法》:重开算法之门,时间复杂度与空间复杂度
|
机器学习/深度学习 存储 算法
颠覆认知!Python算法设计中的时间复杂度与空间复杂度,你真的理解对了吗?
【7月更文挑战第22天】在Python算法设计中,时间与空间复杂度是评估算法效能的核心。时间复杂度不仅限于大O表示法,还涵盖平均与最坏情况分析。空间复杂度虽关注额外存储,但也反映内存效率。平衡二者需视场景而定,如利用原地算法减少内存消耗,或牺牲空间加速执行。算法优化技巧,如分治与动态规划,助你在资源与速度间找寻最优解,从而高效应对大数据挑战。
147 3
|
12月前
|
搜索推荐 算法
插入排序算法的平均时间复杂度解析
【10月更文挑战第12天】 插入排序是一种简单直观的排序算法,通过不断将未排序元素插入到已排序部分的合适位置来完成排序。其平均时间复杂度为$O(n^2)$,适用于小规模或部分有序的数据。尽管效率不高,但在特定场景下仍具优势。
|
12月前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
417 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
存储 算法
算法的时间复杂度和空间复杂度
本文详细讨论了算法的时间复杂度和空间复杂度,包括它们的概念、计算方法和常见复杂度的对比,并通过多个实例解释了如何计算算法的时间和空间复杂度。
769 0
算法的时间复杂度和空间复杂度
|
算法 Python
震惊!Python 算法设计背后,时间复杂度与空间复杂度的惊天秘密大起底!
在 Python 算法设计中,理解并巧妙运用时间复杂度和空间复杂度的知识,是实现高效、优雅代码的必经之路。通过不断地实践和优化,我们能够在这两个因素之间找到最佳的平衡点,创造出性能卓越的程序。
131 5
|
算法 C语言
深入理解算法效率:时间复杂度与空间复杂度
深入理解算法效率:时间复杂度与空间复杂度
|
机器学习/深度学习 存储 算法
算法时间复杂度分析
这篇文章讲解了如何分析算法的时间复杂度,包括关注循环执行次数最多的代码段、总复杂度的确定、嵌套代码复杂度的计算方法,并提供了大O阶的推导步骤和常见时间复杂度的列表,同时还介绍了空间复杂度的概念及其重要性。
|
存储 算法 搜索推荐
深度剖析 Python 算法:时间复杂度与空间复杂度的爱恨情仇,你站哪边?
【7月更文挑战第23天】在Python算法设计中,时间复杂度与空间复杂度如影随形,反映算法效率与资源消耗。时间复杂度揭示算法随输入规模增长的计算趋势,空间复杂度关注额外存储需求。找最大值示例中,两种实现均具O(n)时间与O(1)空间复杂度,但在排序等复杂场景下,如冒泡排序与快速排序,或哈希表与二叉树查找,权衡变得关键。实时系统偏好低时间复杂度算法,存储受限环境则需关注空间效率。最佳选择依应用场景而定,掌握二者平衡,方能编写高效代码。
118 10

热门文章

最新文章