你还在掐表算时间复杂度?

目录

前言

一.算法效率分析:

二.时间复杂度:

2.1时间复杂度度的概念:

2.2大O的渐进表示法:

2.3常见时间复杂度计算案例:

例一:

例二:

 例三:

例四:冒泡排序时间复杂度

​编辑 两层for循环嵌套会让时间复杂度大大增加

例五:二分查找

 例六:计算普通递归的时间复杂度

例七:计算斐波那契数列的时间复杂度

 三.空间复杂度:

 例一:冒泡排序

例二:斐波那契额数列

总结

---

---

前言

        大家好我是Node_Hao,最近开始入门算法了但似乎困难重重,所以我决定从算法最基础的部分开始学习,希望我可以用最通俗易懂的方法帮助你理解时间复杂度和空间复杂度.

---

一.算法效率分析:

        算法效率分析主要有两种:1.时间复杂度,2.空间复杂度.

时间复杂度用来衡量一个算法的运行速度,空间复杂度用来计算一个算法所需的额外空间.在计算机发展初期由于计算机内存特别小,所以非常关注空间复杂度,但随着计算机容量的不断扩大,我们已经不在过分关注空间复杂度,甚至可以牺牲空间换取时间.

二.时间复杂度:

2.1时间复杂度度的概念:

        时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是如果我们每一个算法都上机测试这是很麻烦的,所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

2.2大O的渐进表示法:

        以上内容都是介绍概念与定义,真正的判断方法现在才开始:

        首先大家观察一下这个中学阶段非常熟悉的函数图属实爷青回了,我们平时分析时间复杂度主要用到 :1.y = lgx  3.y=x^2    3.y=x^2.  很明显从运行时间长短可以看出3.y=x^2>3.y=x^2>:1.y = lgx .那么运行速度自然是反过来了.牢记这三个函数之后,你就会发现其实平时遇到的算法体大都是这样了.

        为了更好的理解大O的渐进表示法,我们先从一个简单算法案例入门:

        由图分析这个算法的时间复杂度按理来说应该是 n^2+2*n+10,但我们平时看到的时间复杂度似乎没有这么长度公式,这是为什么?要想知其原因还得看看大O的渐进表示法的定义与概念.

        实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数.
推导大O阶方法：
1、用常数1取代运行时间中的所有加法常数。(那么本例的10可以替换为1)
2、在修改后的运行次数函数中，只保留最高阶项。(那么本例就剩n^2)
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
使用大O的渐进表示法以后，Func1的时间复杂度为：n^2

        通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。
另外有些算法的时间复杂度存在最好、平均和最坏情况：

在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

2.3常见时间复杂度计算案例:

例一:

 

 

例二:

 例三:

例四:冒泡排序时间复杂度

 两层for循环嵌套会让时间复杂度大大增加

例五:二分查找

二分查找的时间复杂度并不像看上去那么简单,这里提供两种计算方法:1.列举法 2.直接计算法

 例六:计算普通递归的时间复杂度

递归时间复杂度=递归次数*执行次数

例七:计算斐波那契数列的时间复杂度

 三.空间复杂度:

讨论完时间复杂度,我们再来谈谈空间复杂度

         空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是额外开辟空间的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法.

 例一:冒泡排序

 冒泡排序创建一个数组之后就不再开辟额外的空间,所以空间复杂度为O(1)

例二:斐波那契额数列

 斐波那契额数列,执行N次就要开辟N个额外空间,所以空间复杂度为O(N)

---

总结

以上就是时间and空间复杂度的全部内容了,想要熟练掌握还需多多实践,如果这么通俗易懂的说法可以帮助你的理解麻烦帅哥美女记得点赞收藏哦!