Python数据结构(时间和空间复杂度)

2022/1/7 11:03:38

本文主要是介绍Python数据结构(时间和空间复杂度),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录

数据结构与算法(Python版)

1.1 算法概念

1.2 时间复杂度

1.3 空间复杂度

1.4 递归

1.5 汉诺塔问题


数据结构与算法(Python版)

  # 1. 入门

1.1 算法概念

概念: 算法就是一个计算过程,解决问题的方法

程序 = 数据结构 + 算法

1.2 时间复杂度

  • 时间复杂度是用来估计算法运行时间的一个式子(单位)

  • 一般来说,时间复杂度高的算法比复杂度低的算法慢

  • 常见的时间复杂度(按照效率排序)

    • O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(n2 log n) < O(n3)

  • 复杂问题的时间复杂度

    • O(n!) O(2n) O(nn) .......

  • 快速判断算法复杂度(适用于大多情况)

    • 确定问题规模 n

    • 循环减半过程 ----- log n

    • k层关于n的循环------- nk

  • 复杂情况:根据算法执行过程判断

1.3 空间复杂度

  • 空间复杂度就是评估内存占用大小的式子

  • 空间复杂度的表示方式与时间复杂度完全一致

    • 算法使用了几个变量: O( 1 )

    • 算法使用了长度为 n 的一维列表:O( n )

    • 算法使用了m行n列的二维列表: O( mn )

  • 空间换时间

1.4 递归

  • 递归的两个特点

    • 调用自身

    • 结束条件

1.5 汉诺塔问题

 

 def hanoi(n, a, b, c):
     if n>0:
         hanoi(n-1, b, c, a)
         print("{} 移动到 {}".format(a, c))
         hanoi(n-1, b, a, c) 
         pass
     pass
 hanoi(64,"A", "B", "C")



这篇关于Python数据结构(时间和空间复杂度)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程