专栏首页freesan44python 算法开发笔记

python 算法开发笔记

前言

最近看完《算法图解》对python的算法有点了解,特记录下来

算法概括

  1. 二分查找的速度比简单查找快得多
  2. 算法运行时间用大O表示法来表示。从起增速的角度度量的。
  3. O(log n) 比O(n)快,需要搜索的元素越多,前者比后者就快越多。
  4. 数组的速度:读取O(1),插入O(n),删除O(n) 链表的速度:读取O(n),插入O(1),删除O(1)

选择排序

#选择排序
def selectSort(arr):
    newArr = []
    oldArr = arr.copy()
    for i in  range(len(arr)):
        mix_index = 0
        #遍历查找oldArr中最低的元素,并删除添加到新数组中
        for i in range(1,len(oldArr)):
            if oldArr[mix_index] > oldArr[i]:
                mix_index = i
        newArr.append(oldArr[mix_index])
        oldArr.pop(mix_index)

    return newArr

递归

  1. 递归函数有两个要点: 1、基线条件,就是停止调用,跳出递归的条件 2、递归条件,指函数调用自己
  2. 如果你对递归有深入的认识,函数式编程语言学习起来将会更容易。Haskell等函数式编程语言没有循环,因此你只能使用递归来编写函数。

快速排序

  1. 工作原理: 1、找出简单的基线条件 2、确定如何缩小问题的规模,使其符合基线条件
  2. 归纳证明是一种证明算法行之有效的方式,它分两步:基线条件和归纳条件。归纳条件就是证明对一个元素管用、对两个、三个元素也管用,以此类推。
  3. 快速排序的平均运行时间是O(nlogn),最高是O(n2)
#快速排序
def quickSort(arr):
    #基线条件
    if len(arr) < 2:
        return arr
    else:
        #基准值
        pivot = arr[0]
        less = []
        gretter = []
        for i in arr[1:]:
            if i > pivot:
                gretter.append(i)
            else:
                less.append(i)
        #用递归进行反复排序
        return quickSort(less) + [pivot] + quickSort(gretter)

散列函数

  1. 在python和OC里面,就是字典的称呼,也称为映射、散列映射、关联数组。散列函数的运行速度是O(1)。
  2. 散列函数的性能: 平均情况:查找O(1),插入O(1),删除O(1) 最慢情况:查找O(n),插入O(n),删除O(n)
  3. 优化散列函数: 1、较低的填装因子,不要填满全部空位; 2、良好的散列函数,因子要均匀散布,映射范围要尽可能地大。

广度优先搜索

  1. 属于图算法的一种,擅长找出两者最短距离,解决最短路径问题
  2. 步骤: 1、使用图来建立问题模型 2、使用广度优先搜索解决问题
  3. 查找到f的路径:
#广度优先搜索
#广度优先搜索
from collections import deque #引入堆(队列)
def search_queue(dic):
    searchQueue = deque()
    searchQueue.append(dic['a'])
    searched = [] #已搜索队列
    while searchQueue:#只要队列不为空
        letter = searchQueue.popleft()
        if letter not in searched:
            if letter[-1] == 'f':
                print("找到终点了")
                return True
            else:
                for each in letter:
                    searchQueue.append(dic[each])
                searched.append(letter)
    return False

 dic = {}
    dic['a'] = ['b','c']
    dic['b'] = ['d']
    dic['c'] = ['e']
    dic['d'] = ['g']
    dic['e'] = ['f']
    dic['f'] = []
    dic['g'] = []
    print(search_queue(dic))

狄克斯特拉算法

  1. 在每个节点中加上权重,是针对加权图进行计算,但只适用于有向无环图DAG,且不能用于有负权边的。
  2. 对于有负权边的图,找出最短路径,可用贝尔曼-福德算法

贪婪算法

  1. 每步都选择局部最优解,未必是整体的最优解,但会非常接近最优解,速度快
  2. NP完全问题,并没有快速解决的方案,最佳的做法是使用近似算法
  3. 贪婪算法易于实现,运行速度快,是不错的近似算法
  4. NP完全问题的特征: 1、元素较少时算法运行速度非常快,但随着元素数量的增加,速度会变得非常慢。 2、涉及“所有组合”的问题通常都是NP完全问题 3、不能把问题分成小问题,必须考虑各种可能的情况。这可能是NP完全问题。 4、如果问题涉及序列(如旅行商问题洪的城市序列)且难以解决,它可能就是NP完全问题。 5、如果问题涉及集合(如广播台集合)且难以解决,它可能就是NP完全问题。 6、如果问题可转换为集合覆盖问题或旅行商问题,那它肯定是NP完全问题

动态规划

  1. 动态规划可以在给定约束条件下找到最优解。
  2. 在问题可分解为彼此独立且离散的子问题时,就可使用动态规划来解决,每种动态规划解决方案都涉及网格。
  3. 每个单元格都是一个子问题,因此你需要考虑如何将问题分解为子问题
  4. 没有放之四海而皆准的计算动态规划解决方案的公式。

K最近邻算法

  1. 大数据比较常用的算法,抽取特征值计算与其他元素的最近值来分类
  2. 回归就是预测的结果,分类就是编组
  3. 计算两个元素的距离时,有使用距离公式,也有使用余弦相似度

其他

  1. 二叉树,如果对数据库或高级数据结构感兴趣,可以研究以下数据结构:B树,红黑树,堆,伸展树
  2. 反向索引,key为单词,值为包含指定单词的页面,常用于创建搜索引擎
  3. 傅里叶变换,太多地方用到,只要能转换成数字信号等元素都能用到这个算法
  4. 并行算法: 1、分布式算法,MapReduce,可以用Apache Hadoop来使用它 2、映射(Map)函数,把一个数组转换成另一个数组 3、归并(reduce)函数,把一个数组转换成一个元素
  5. 布隆过滤器,概率性数据结构,主要用在去重,监测是否已存在,答案有可能正确,也有可能不正确 HyperLogLog,类似布隆过滤器的算法
  6. SHA算法,散列函数,根据字符串生成另一个字符串,用于比较文件密码 局部敏感的散列算法,Simhash,可以监测内容是否大致相同,比较相似度
  7. Diffie——Hellman密钥交换,还有RSA,就是公钥私钥算法。
  8. 线性规划,所有图算法都可以用线性规划来时限,是比较宽泛的框架,其中之一是Simplex算法,如果就查找最优解,可以研究研究线性规划

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 70. 爬楼梯

    动态规划 到达第 i 阶的方法总数就是到第 (i−1) 阶和第 (i−2) 阶的方法数之和。

    freesan44
  • Xcode8 脚本打包ipa

    1,生成Archive: 工程文件把Automatically manage siging打钩 xcodebuild -scheme GDNXBankPro...

    freesan44
  • App Store把app的评论扒下来

    链接:https://github.com/freesan44/AppReviews

    freesan44
  • Python之字典

    py3study
  • 这拖拉机你能开算我输:美国少女“揭秘”现代拖拉机驾驶室,Jeff Dean都看呆了

    在视频里,她不仅展示了现代拖拉机驾驶室的内部情况,还亲自上手演示、解说了一把拖拉机驾驶技术。

    量子位
  • 怎样开始制作一款微信小游戏?

    至于这个游戏是什么类型?竞技?休闲?益智?管它的,我连这个小游戏该叫什么名字都不知道。

    沙因Sign
  • 竞争红海下,游戏开发者如何突围终极指南

    内容来源:2018 年 09 月 08 日,Cocos CEO王哲在“2018 RTC 实时互联网大会”进行《Cocos 引擎助力游戏开发者突围》的演讲分享。I...

    IT大咖说
  • 推荐系统那点事

    大数据文摘
  • 比DGL快14倍:PyTorch图神经网络库PyG上线了

    项目链接:https://github.com/rusty1s/pytorch_geometric

    机器之心
  • 比DGL快14倍:PyTorch图神经网络库PyG上线了

    项目链接:https://github.com/rusty1s/pytorch_geometric

    刀刀老高

扫码关注云+社区

领取腾讯云代金券