专栏首页诡途的python路02 复杂度分析_pythoner学习数据结构与算法系列

02 复杂度分析_pythoner学习数据结构与算法系列

系列目录

01 ~ 10篇

11 ~ 20篇

01 数据结构与算法总览

11 二分查找

02 复杂度分析

12 动态规划

03 数组、链表、跳表

13 字典树和并查集

04 栈、队列、优先队列、双端队列

14 高级搜索

05 哈希表、映射、集合

15 红黑树和AVL树

06 树、二叉树、二叉搜索树

16 位运算

07 泛型递归、树的递归

17 布隆过滤器和LRU缓存

08 分治、回溯

18 排序算法

09 深度优先搜索和广度优先搜索

19 高级动态规划

10 贪心算法

20 字符串算法

思维导图

基本概念

  • 算法: 解决一个问题的完整性描述
  • 算法的效率:
    • 时间复杂度:评估执行程序所需的时间。可以估算出程序对处理器的使用程度。
    • 空间复杂度:评估执行程序所需的存储空间。可以估算出程序对计算机内存的使用程度。

    设计算法时,时间复杂度要比空间复杂度更容易出问题,所以一般情况一下我们只对时间复杂度进行研究。一般面试或者工作的时候没有特别说明的话,复杂度就是指时间复杂度。

七种常见时间复杂度

  • O(1):Constant Complexity 常数复杂度
  • O(log n):Logarithmic Complexity 对数复杂度
  • O(n):Linear Complexity 线性复杂度
  • O(n^2):N square Complexity 平方复杂度
  • O(n^3):N cube Complexity 立方复杂度
  • O(2^n):Exxponential Growth 指数复杂度
  • O(n!): Factorial 阶乘复杂度

【1】映射 O 表示它的复杂度是关于n的什么一个函数,可以理解为映射, 类似于函数里的f(x),f表示的是关于x的一种映射关系

【2】时间复杂度不考虑系数k,例:

  • ① 只要是常数次的就是 O(1),不单指运算1次 可能是2次、3次、、、etc
  • ② O(n)不单指运算n次,也可能是2n次、3n次、、、etc

时间复杂度分析

分析方法: 通过一段代码 根据n的不同情况,会运行多少次,来判断该段代码的时间复杂度

样例分析: 一 、O(1):Constant Complexity 常数复杂度

#不论n=?,只执行一次print
#即print(或者循环体代码)执行次数相对n的映射关系是常数C
#即print(或者循环体代码)执行次数不受n值得影响
def f  (n=100):
	print("你输入的是:",n)
#print 3次,时间复杂度是O(1)|常熟复杂度,没有 O(3)这种说法
#不论n=?,只执行3次print
def f  (n=100):
	print("你输入的是:",n)
	print("你需要输入的是:",n)
	print("你已经完成了:",n)

二、O(n):Linear Complexity 线性时间复杂度

#假设 print执行次数为y
#则执行次数y与输入n满足:y=n的线性关系
#print(或循环体代码)时间复杂度是O(n)
#或称为Linear Complexity 线性时间复杂度
def f  (n=10):
	for i in range(n):
		print("当前是第{}次执行".format(i))
		
#while写法
def f  (n=10,i=1):
    while i <=n:
        print("当前是第{}次执行".format(i))
        i+=1

三、O(n^2):N square Complexity 平方

#嵌套循环
#同理,假设 print执行次数为y
#则执行次数y与输入n满足:y=n^2的线性关系
#print(或循环体代码)时间复杂度是O(n^2)
#或称为N square Complexity 平方时间复杂度
def f(n=5):
    for i in range(n):
        for j in range(n):
            print("当前是第{}组,第{}次".format(i,j))

如果是i,j,k三层嵌套就是O(n^3) 立方的时间复杂度

#拓展———两个并列循环——O(n)线性时间复杂度
#print执行次数为y与输入n满足的是:y=2n的线性关系
#时间复杂度不考虑系数k,所以还是O(n)线性时间复杂度
def f(n=5):
    for i in range(n):
    	print(i)
    for j in range(n):
        print(j)

四、O(log n):Logarithmic Complexity 对数复杂度

#O(log n)的时间复杂度,
#或者O(log2(n)+1)的时间复杂度,不考虑常数项O(log n)
def f(n=100):
	i=1
	while i <n:
	    print(i)
	    i=i*2

归纳推导:

输入(n)

print次数y

1

1

2

2

4

3

8

4

16

5

32

6

64

7

n

log2(n)+1

  • 所以对数的实际映射通项应该是O(logk(n)+C)
  • 上例中 i=i*2 的2换为3,时间复杂度就是O(log3(n)+1)

TIPS:关于python中的log函数

#log在python中的简单计算
#默认log=ln,其他底用logk()表示
import numpy  as np
import  math
print(math.log(4))
print(math.log10(100),np.log10(100))
print(math.log2(4),np.log2(4))
print(math.log(np.e),np.log(np.e))

五、O(2^n):Exxponential Growth 指数复杂度

#Fibonacci斐波那契数列
#指数复杂度通项O(k^n),Fibonacci是O(2^n)
#详细分析过程见下一段:递归下的时间复杂度分析
def fib(n):
    if  n<=2:
        return n
    else:
        return fib(n-1)+fib(n-2)

递归下的时间复杂度分析

一、画递归树/状态树

求Fibonacci的第n项 :F(n)=F(n-1)+F(n-2) 暴力解法: 直接递归,代码见上段:指数复杂度,时间复杂度 O(2^n)

F(6)的状态树:

  • 每多展开一层,节点数就是上一层的两倍
  • 总节点数就是2^n(指数级增长)

优化:

  • 很多重复结果多次计算冗余;
  • 可以加一个中间缓存,把中间结果缓存下来;
  • 或者直接使用一个循环来写;

二、主定理(Master theorem)

主定理主要是用来解决所有递归函数时间复杂度计算 任何分治或者递归的函数都可以用主定理计算出时间复杂度

常见的四种场景:

  • 一维的二分查找 O(logn)
  • 二叉树遍历O(n):每个节点都会访问且仅访问一次
  • 二维矩阵(有序)的二分查找O(n)
  • 归并排序——所有排序的时间复杂度都是O(nlogn)

三、常见面试题

1.二叉树的遍历-前序、中序、后序 :时间复杂度是多少? 2.图的遍历,时间复杂度是多少?

  • O(n),n代表二叉树的节点总数
  • 通过主定理得到
  • 或者遍历(不论前、中、后序),每个节点都会访问且仅访问一次, 复杂度是线性于树的节点数的,所以是 O(n)的时间复杂度
  • 同理(图的节点也是每个都会访问且仅访问一次):图的遍历, 时间复杂度也是O(n),n是图的结点总数

搜索算法:DFS(深度优先搜索)、BFS(广度优先搜索),时间复杂度是多少?

  • 不论DFS还是BFS时间复杂度都是 O(n),n是空间结点总数,每个节点都要 访问且仅访问一次

二分查找:时间复杂度是多少?

  • 一维数组的二分查找是O(logn)
  • 有序二维矩阵的二分查找是O(n)

时间复杂度曲线图

程序员职业素养:

  • 一定要对自己程序的时间和空间复杂度有所了解,并养成习惯,写完每段代码之后,能够下意识地分析出你这段代码的时间和空间复杂度
  • 能够用最简洁的时间和空间复杂度完成这段程序是顶尖职业选手必备的素养

时间复杂度优化

时间复杂度优化的简单样例,体验不同程序达成同一个目标的时间复杂度变化

题目:1+2+3+…+n

#解法一:暴力法累加
#时间复杂度 O(n)
def add_n(n):
	result = 0
	for i in range(1,n+1):
		result+=i
	return result
#解法二:求和公式 sum = n(n+1)/2
#时间复杂度 O(1)
#注意此处不是n^2的复杂度
def add_n(n):
	return n*(n+1)/2

一个好的时间复杂度程序,可以大大降低工程成本,提升工程效率

延伸性阅读资料

上一篇: 01 数据结构与算法总览 下一篇: 03 数组、链表、跳表

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 服务器上安装Mysql8.0

    然后 创建目录mysql,我一般软件放在 /usr/local 下, cd 到/usr/local 下mkdir mysql 然后进入目录,下载 mysql8...

    诡途
  • python初学者笔记—入门基础知识

    变量:存储数据的容器,我们可以通过变量来操作数据 我们在创建变量时会在内存中开辟一个空间,可以存储不同类型的数据。

    诡途
  • 面向对象语言的三大特征: 封装 继承 多态(二)——继承

    子类去重写父类中的方法, 当子类重写了父类中的方法,子类再调用该方法时 调用的是子类重写之后的

    诡途
  • 数据结构与算法 1-4 常见时间复杂度与大小关系

    本系列是我在学习《基于Python的数据结构》时候的笔记。本小节主要介绍一些常见的时间复杂度以及它们之间的大小关系。

    触摸壹缕阳光
  • 昨天的文章,有朋友给出"更好的"解法,其实并不是...

    昨天推送一道题目分析,一方面学习一个颇具特色的数组,它的取值不大于数组长度;另一方面通过这道题充分体会算法分析、逻辑推理的重要性。只有做好充分的分析,才可能写出...

    double
  • 数据结构算法入门--一文了解什么是复杂度

    最近会开始更新一个数据结构算法的学习系列,同时不定期更新 leetcode 的刷题。

    kbsc13
  • 常用算法解析

    算法基础:概念,时间复杂度,空间复杂度,常见算法以及复杂度计算 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?...

    wangxl
  • 笔试常考题型之时间复杂度

    Zoctopus
  • 笔试常考题型之时间复杂度

    Zoctopus
  • 数据结构和算法

    10个算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。

    分母为零

扫码关注云+社区

领取腾讯云代金券