2021-02-19 算法简介

1458-Hayden

发表文章数:32

热门标签

,
首页 » Python » 正文

算法的五大特性

  1. 输入: 算法具有0个或多个输入
  2. 输出: 算法至少有1个或多个输出
  3. 有穷性: 算法在有限的步骤之后会自动结束而不会无限循环,并且每一个步骤可以在可接受的时间内完成
  4. 确定性:算法中的每一步都有确定的含义,不会出现二义性
  5. 可行性:算法的每一步都是可行的,也就是说每一步都能够执行有限的次数完成

算法效率衡量

我们假定计算机执行算法每一个基本操作的时间是固定的一个时间单位,那么有多少个基本操作就代表会花费多少时间单位。由此可以忽略机器环境的影响而客观的反应算法的时间效率。

大O记法

对于单调的整数函数f,如果存在一个整数函数g和实常数c>0,使得对于充分大的n总有f(n)<=c*g(n),就说函数g是f的一个渐近函数(忽略常数),记为f(n)=O(g(n))。也就是说,在趋向无穷的极限意义下,函数f的增长速度受到函数g的约束,亦即函数f与函数g的特征相似。
时间复杂度:假设存在函数g,使得算法A处理规模为n的问题示例所用时间为T(n)=O(g(n)),则称O(g(n))为算法A的渐近时间复杂度,简称时间复杂度,记为T(n)
分析算法时,存在几种可能的考虑:

  • 算法完成工作最少需要多少基本操作,即最优时间复杂度
  • 算法完成工作最多需要多少基本操作,即最坏时间复杂度
  • 算法完成工作平均需要多少基本操作,即平均时间复杂度

时间复杂度的几条基本计算规则

  • 基本操作,即只有常数项,认为其时间复杂度为O(1)
  • 顺序结构,时间复杂度按加法进行计算
  • 循环结构,时间复杂度按乘法进行计算
  • 分支结构,时间复杂度取最大值
  • 判断一个算法的效率时,往往只需要关注操作数量的最高次项,其它次要项和常数项可以忽略
  • 在没有特殊说明时,我们所分析的算法的时间复杂度都是指最坏时间复杂度

常见时间复杂度之间的关系

算法效率关系
2021-02-19 算法简介

O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2^n) < O(n!) < O(n^n)

timeit模块

timeit模块可以用来测试一小段Python代码的执行速度。
class timeit.Timer(stmt=‘pass’, setup=‘pass’, timer=<timer function>)
Timer是测量小段代码执行速度的类;stmt参数是要测试的代码语句(statment);setup参数是运行代码时需要的设置;timer参数是一个定时器函数,与平台有关。
timeit.Timer.timeit(number=1000000)
Timer类中测试语句执行速度的对象方法。number参数是测试代码时的测试次数,默认为1000000次。方法返回执行代码的平均耗时,一个float类型的秒数。
示例代码:

def test1():
   l = []
   for i in range(1000):
      l = l + [i]
def test2():
   l = []
   for i in range(1000):
      l.append(i)
def test3():
   l = [i for i in range(1000)]
def test4():
   l = list(range(1000))

from timeit import Timer

t1 = Timer("test1()", "from __main__ import test1")
print("concat ",t1.timeit(number=1000), "seconds")
t2 = Timer("test2()", "from __main__ import test2")
print("append ",t2.timeit(number=1000), "seconds")
t3 = Timer("test3()", "from __main__ import test3")
print("comprehension ",t3.timeit(number=1000), "seconds")
t4 = Timer("test4()", "from __main__ import test4")
print("list range ",t4.timeit(number=1000), "seconds")

# ('concat ', 1.7890608310699463, 'seconds')
# ('append ', 0.13796091079711914, 'seconds')
# ('comprehension ', 0.05671119689941406, 'seconds')
# ('list range ', 0.014147043228149414, 'seconds')

list内置操作的时间复杂度2021-02-19 算法简介

dict内置操作的时间复杂度

2021-02-19 算法简介

未经允许不得转载:作者:1458-Hayden, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《2021-02-19 算法简介》 发布于2021-02-20

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录