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 条评论
登录 后参与评论

相关文章

来自专栏蜉蝣禅修之道

优化后的Levensthein distance算法实现

3915
来自专栏数据结构与算法

Day4晚笔记

数据结构 并查集:捆绑两个点的信息,判断对错 倍增:LCA, 字符串 hash,模拟, 最小表示法 给定一个环状字符串,切开,使得字符串的字典序最小 图和树 割...

2664
来自专栏null的专栏

数据结构和算法——用动态规划求解最短路径问题

一、动态规划求解问题的思路     在《算法导论》上,动态规划的求解过程主要分为如下的四步: 描述最优解的结构 递归定义最优解的值 按自底向上的方式计算最优解的...

4775
来自专栏数据结构与算法

Vijos / 题库 / 输油管道问题

背景 想念car的GF,car就出了道水题! 描述 某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道...

37611
来自专栏温安适的blog

图论-网络流

3834
来自专栏算法修养

整数划分总结

整数划分问题: 笼统上说就是将一根整数划分成若干个整数之和的方案数。整数划分很多不同的问法,也有隐晦的问法。比如n个苹果放到m个盘子里,比如n个砖块堆成m个...

3216
来自专栏C语言及其他语言

【每日一题】1445: [蓝桥杯][历届试题]最大子阵

节日快乐,筒子们! 不过小编还是给大家准备了每日一题! 2333 题目描述 给定一个n*m的矩阵A,求A中的一个非空子矩阵,使这个子矩阵中的元素和最大。 其...

3878
来自专栏程序员叨叨叨

7.1 Cg 关键字第 7 章 输入\输出与语义绑定

第三章从 GPU 运行原理和数据流程的角度阐述了顶点着色程序和片段着色程序的输入输出,即,应用程序(宿主程序)将图元信息(顶点位置、法向量、纹理坐标等)传递给顶...

1553
来自专栏算法channel

图算法|Prim算法求最小生成树

01 — 一个实际问题 要在n个城市之间铺设光缆,要求有2个: 这 n 个城市的任意两个之间都可以通信; 铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同,...

9647
来自专栏计算机视觉与深度学习基础

HDU4832

由于水平和竖直相互独立,所以可以分开计数,最后再用组合数算一下,万年老坑long long #include<cstdio> #include<iostream...

20710

扫码关注云+社区

领取腾讯云代金券