侧边栏壁纸
博主头像
Wyatt博主等级

Done is better than perfect!

  • 累计撰写 103 篇文章
  • 累计创建 31 个标签
  • 累计收到 7 条评论

00|复杂度分析基础知识

Wyatt
2020-10-13 / 0 评论 / 0 点赞 / 289 阅读 / 1,549 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2020-12-03,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

一.简介

1.1 何为“复杂度”

复杂度:指为了执行目标程序,所需要的计算资源与“问题规模”之间的函数关系。

  • 时间复杂度:是指执行当前算法所消耗的时间
  • 空间复杂度:是指执行当前算法需要占用多少内存空间

1.2 问题规模

"问题规模" 是需要根据具体问题来定义的, 通常会用若干个自然数来定义,当然也是根据具体场景和分析侧重来定义的。因此,定义 "问题规模" 本身就是分析过程中的一个很重要的步骤。

1.3 大O符号含义

用大O记法表示的复杂度,叫做渐近复杂度(asymptotic complexity),通常大家说的"分析算法复杂度"指的就是渐近复杂度分析。
引用知乎的一段话:

大O符号是一种算法「复杂度」的「相对」「表示」方式。

  • 相对(relative):你只能比较相同的事物。你不能把一个做算数乘法的算法和排序整数列表的算法进行比较。但是,比较2个算法所做的算术操作(一个做乘法,一个做加法)将会告诉你一些有意义的东西;
  • 表示(representation):大O(用它最简单的形式)把算法间的比较简化为了一个单一变量。这个变量的选择基于观察或假设。

二.类型

常见复杂度表示:

  • O(1): Constant Complexity: Constant 常数复杂度
  • O(log(n)): Logarithmic Complexity: 对数复杂度
  • O(n): Linear Complexity: 线性时间复杂度
  • O(n^2): N square Complexity 平⽅
  • O(n^3): N square Complexity ⽴⽅
  • O(2^n): Exponential Growth 指数
  • O(n!): Factorial 阶乘

2.1 O(1)

# 程序只执行一次
print("hello world")

2.2 O(n)

# 程序线性增长执行
n = 10
for i in range(n):
    print("hello world")

2.3 O(n^2)

# 程序嵌套循环,执行n^2次
n = 10
for i in range(n):
    for j in range(n):
        print("hello world")

2.4 O(log(n))

# 程序步长为2(或者更大),反推其执行次数为log(n)
n = 10
for i in range(0, n, 2):
    print("hello world",i)

2.5 O(k^n)

# pow(n,k)为最终执行的次数,以下为举例
n = 10
k = 3
for i in range(pow(n, k)):
    print("hello world", i)


2.6 O(n!)

# factorial(n)为最终执行的次数,以下为举例
import math
n = 5
for i in range(math.factorial(n)):
    print("hello world", i)


三.小结

以上例子证明了:“print”函数执行多少次,该算法的时间复杂度即为O(x)多少。
借用极客时间的一张图,如下:
复杂度图

0

评论区