1. 蓝洛水深首页
  2. 教程
  3. 软件

Python自学Day16 Python语言进阶之数据结构和算法

Python语言进阶

数据结构和算法

算法:解决问题的方法和步骤

评价算法的好坏:渐近时间复杂度和渐近空间复杂度。

渐近时间复杂度的大O标记:

Python自学Day16 Python语言进阶之数据结构和算法– 常量时间复杂度 – 布隆过滤器 / 哈希存储

Python自学Day16 Python语言进阶之数据结构和算法– 对数时间复杂度 – 折半查找(二分查找)

Python自学Day16 Python语言进阶之数据结构和算法– 线性时间复杂度 – 顺序查找 / 桶排序

Python自学Day16 Python语言进阶之数据结构和算法– 对数线性时间复杂度 – 高级排序算法(归并排序、快速排序)

Python自学Day16 Python语言进阶之数据结构和算法– 平方时间复杂度 – 简单排序算法(选择排序、插入排序、冒泡排序)

Python自学Day16 Python语言进阶之数据结构和算法– 立方时间复杂度 – Floyd算法 / 矩阵乘法运算

Python自学Day16 Python语言进阶之数据结构和算法– 几何级数时间复杂度 – 汉诺塔

Python自学Day16 Python语言进阶之数据结构和算法– 阶乘时间复杂度 – 旅行经销商问题 – NP

Python自学Day16 Python语言进阶之数据结构和算法

Python自学Day16 Python语言进阶之数据结构和算法

排序算法(选择、冒泡和归并)和查找算法(顺序和折半)

使用生成式(推导式)语法

嵌套的列表

heapq、itertools等的用法

collections模块下的工具类

常用算法:

  • 穷举法 – 又称为暴力破解法,对所有的可能性进行验证,直到找到正确答案。
  • 贪婪法 – 在对问题求解时,总是做出在当前看来
  • 最好的选择,不追求最优解,快速找到满意解。
  • 分治法 – 把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题,直到可以直接求解的程度,最后将子问题的解进行合并得到原问题的解。
  • 回溯法 – 回溯法又称为试探法,按选优条件向前搜索,当搜索到某一步发现原先选择并不优或达不到目标时,就退回一步重新选择。
  • 动态规划 – 基本思想也是将待求解问题分解成若干个子问题,先求解并保存这些子问题的解,避免产生大量的重复运算。

穷举法例子:百钱百鸡和五人分鱼。

贪婪法例子:假设小偷有一个背包,最多能装20公斤赃物,他闯入一户人家,发现如下表所示的物品。很显然,他不能把所有物品都装进背包,所以必须确定拿走哪些物品,留下哪些物品。

名称价格(美元) 重量(kg)
电脑20020
收音机204
17510
花瓶502
101
油画909

分治法例子:快速排序。

回溯法例子:骑士巡逻。

动态规划例子1:斐波拉切数列。(不使用动态规划将会是几何级数复杂度)

动态规划例子2:子列表元素之和的最大值。(使用动态规划可以避免二重循环)

 

本文来自这个系列长期转载Python-100-Days ,本文观点不代表蓝洛水深立场,转载请联系原作者。

发表评论

登录后才能评论

联系我们

455922333

在线咨询:
点击这里给我发消息
邮件:me@llss.us

工作时间:大部分和你一样