首页 / 算法 / 【算法图解】学习笔记

【算法图解】学习笔记

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【算法图解】学习笔记，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含8572字，纯文字阅读大概需要13分钟。

内容图文

一、算法简介

1.1 二分查找

对于包含n个元素的列表，用二分查找最多需要log₂n步，而简单查找最多需要n步
仅当列表是有序的时候，二分查找才管用

代码实现：

def binary_search(list, item):
    low = 0
    high = len(list) - 1
    
    while low <= high:
        mid = (low + high)
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None

my_list = [1, 3, 5, 7, 9]

print(binary_search(my_list, 3))

运行时间：对数时间

1.2 大O表示法

大O表示法是一种特殊的表示法，指出了算法的速度
大O表示法让你能够比较操作数，它指出了算法运行时间的增速。
大O 表示法指出了最糟情况下的运行时间

常见的大O运行时间：

O ( l o g n ) O(log n) O(logn)，对数时间，包括二分查找。
O ( n ) O(n) O(n)，线性时间，包括简单查找。
O ( n l o g n ) O(nlog n) O(nlogn)，包括快速排序——一种速度较快的排序算法。
O ( n 2 ) O(n^2) O(n2)，包括选择排序——一种速度较慢的排序算法。

O ( n ! ) O(n!) O(n!)，包括旅行商问题的解决方案——一种非常慢的算法。

大O运行时间	算法
O ( 1 ) O(1) O(1)（常量时间）	散列表
O ( l o g n ) O(log n) O(logn)（对数时间）	二分查找
O ( n ) O(n) O(n)（线性时间）	简单查找
O ( n l o g n ) O(nlog n) O(nlogn)	快速排序
O ( n 2 ) O(n^2) O(n2)	选择排序
O ( n ! ) O(n!) O(n!)	旅行商问题

启示：
- 算法的速度指的并非时间，而是操作数的增速。
- 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。
- 算法的运行时间用大O表示法表示。
- O ( l o g n ) O(log n) O(logn)比 O ( n ) O(n) O(n)快，当需要搜索的元素越多时，前者比后者快得越多。

二、选择排序

2.1 数组与链表

数组
链表：链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起

数组与链表运行时间：

	数组	链表
读取	O ( 1 ) O(1) O(1)	O ( n ) O(n) O(n)
输入	O ( n ) O(n) O(n)	O ( 1 ) O(1) O(1)
删除	O ( n ) O(n) O(n)	O ( 1 ) O(1) O(1)

索引：元素的位置称为索引
插入：使用链表时，插入元素很简单，只需修改它前面的那个元素指向的地址。而使用数组时，则必须将后面的元素都向后移。当需要在中间插入元素时，链表是更好的选择。
删除：当删除元素时，链表是更好的选择。

2.2 选择排序

遍历整个列表，找出最大的元素，并添加到一个新列表中。继续这样做，将得到一个有序列表
运行时间： O ( n 2 ) O(n^2) O(n2)

代码实现：

#找到最小值
def findSmallest(arr):
    smallest = arr[0]
    smallest_index = 0
    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index

#把最小值加入新数组
def selectionSort(arr):
    newArr = []
    for i in range(len(arr)):
        smallest = findSmallest(arr)
        newArr.append(arr.pop(smallest))
    return newArr

print(selectionSort([5, 3, 6, 2, 10]))

三、递归

递归：调用自己的函数
递归条件：递归条件指的是函数调用自己
基线条件：基线条件指的是函数不再调用自己，从而避免形成无限循环。
栈
递归调用栈
栈的操作：压入和弹出

四、快速排序

4.1 分而治之（D&C）

一种著名的递归式问题解决方法。
步骤
- 找出基线条件
- 确定如何缩小问题的规模，使其符合基线条件

4.2 快速排序

步骤：
- 从数组中选择一个元素，这个元素被称为基准值，一般将数组的第一个元素用作基准值
- 分区：找出比基准值小的元素以及比基准值大的元素：
  - 一个由所有小于基准值的数字组成的子数组
  - 基准值
  - 一个由所有大于基准值的数组组成的子数组
- 对两个子数组进行快速排序

代码实现：

def quicksort(array):
    if len(array) < 2:
        return array
    else:
        pivot = array[0]
        less = [i for i in array[1:] if i <= pivot]
        greater = [i for i in array[1:] if i > pivot]
        return quicksort(less) + [pivot] + quicksort(greater)

print(quicksort([10, 5, 2, 3]))

4.3 再谈大O表示法

快速排序的性能高度依赖于你选择的基准值

五、散列表

5.1 散列函数

将输入映射到数字
要求：
- 一致性
- 一一对应
散列函数总是将同样的输入映射到相同的索引
散列函数将不同的输入映射到不同的索引
散列函数知道数组有多大，只返回有效的索引

5.2 散列表

散列表：散列映射，映射，字典，关联数组
python提供的散列表为字典
散列表的应用：
- 模拟映射关系
- 防止重复
- 用作缓存
  - 优点：用户更快地看到网页，服务器工作减少
冲突：给两个键分配的位置相同
- 反省：
  - 散列函数很重要。尽量让散列函数将键均匀地映射到散列表的不同位置。
  - 如果散列表存储的链表过长，散列表的速度将急剧下降

性能：散列表的查找、插入和删除速度都非常快

	散列表（平均情况）	散列表（最糟情况）	数组	链
读取	O ( 1 ) O(1) O(1)	O ( n ) O(n) O(n)	O ( 1 ) O(1) O(1)	O ( n ) O(n) O(n)
输入	O ( 1 ) O(1) O(1)	O ( n ) O(n) O(n)	O ( n ) O(n) O(n)	O ( 1 ) O(1) O(1)
删除	O ( 1 ) O(1) O(1)	O ( n ) O(n) O(n)	O ( n ) O(n) O(n)	O ( 1 ) O(1) O(1)

5.3 装填因子

装填因子=散列表包含的元素数 / 位置总数
装填因子=1：最佳情况，每个元素都有自己的位置
装填因子>1：元素数量超出了数组的位置数
当填装因子开始增大，你就需要在散列表中添加位置，这被称为调整长度
填装因子越低，发生冲突的可能性越小，散列表的性能越高。
经验规律：一旦填装因子大于0.7，就调整散列表的长度。

六、广度优先搜索

6.1 最短路径问题

步骤：
- 使用图来建立问题模型
- 使用广度优先搜索解决问题

6.2 广度优先搜索

用于图的查找算法
应用：
- 第一类问题：寻找路径：从节点A出发，有前往节点B的路径吗？
- 第二类问题：查找最短路径（段数最少的路径，而不是最快路径）：从节点A出发，前往节点B的哪条路径最短？
查找最短路径：
- 在广度优先搜索的执行过程中，搜索范围从起点开始逐渐向外延伸，即先检查一度关系，再检查二度关系
- 只有按添加顺序查找时，才能实现这样的目的
队列：
- 操作：入队和出队
- 操作顺序：先进先出
  
  数据结构操作顺序
  栈先进后出
  队列先进先出
实现图
- 有向图：其中的关系是单向的
- 无向图：没有箭头，直接相连的节点互为关系
算法工作原理：
- 创建一个队列，用于存储要检查的人
- 从队列中弹出一个人
- 检查这个人是否是目标
- 将这个人的所有邻居都列入队列

数据结构	操作顺序
栈	先进后出
队列	先进先出

算法实现：

from collections import deque

graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []

def person_is_seller(name):
    return name[-1] == 'm'

def search(name):
    search_queue = deque()
    search_queue += graph[name]
    searched = []
    while search_queue:
        person = search_queue.popleft()
        if not person in searched:
            if person_is_seller(person):
                print(person + " is a mango seller!")
                return True
            else:
                search_queue += graph[person]
                searched.append(person)
    return False

search("you")

运行时间： O ( V + E ) O(V+E) O(V+E)，V为顶点数，E为边数

七、狄克斯特拉算法

7.1 使用狄克斯特拉算法

目的：找出最快路径
步骤：
- 找出“最便宜”的节点，即可在最短时间内到达的节点
- 更新该节点的邻居的开销，其含义将稍后介绍
- 重复这个过程，直到对图中的每个节点都这样做了
- 计算最终路径

7.2 术语

权重：狄克斯特拉算法用于每条边都有关联数字的图，这些数字称为权重
加权图：带权重的图称为加权图。要计算加权图中的最短路径，可使用狄克斯特拉算法
非加权图：不带权重的图称为非加权图。要计算非加权图中的最短路径，可使用广度优先搜索

7.3 实现

graph = {}
graph["you"] = ["alice", "bob", "claire"]

graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2

graph["a"] = {}
graph["a"]["fin"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5

graph["fin"] = {}

infinity = float("inf")

infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity

parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None

processed = []

def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

node = find_lowest_cost_node(costs)
while node is not None:
    cost = costs[node]
    neighbors = graph[node]
    for n in neighbors.keys():
        new_cost = cost + neighbors[n]
        if costs[n] > new_cost:
            costs[n] = new_cost
            parents[n] = node
    processed.append(node)
    node = find_lowest_cost_node(costs)

八、贪婪算法

8.1 教室调度问题

思想：
- 选出结束最早的课，它就是要在这间教室上的第一堂课。
- 接下来，必须选择第一堂课结束后才开始的课。同样，你选择结束最早的课，这将是要在这间教室上的第二堂课。

8.2 背包问题

思想：
- 盗窃可装入背包的最贵商品。
- 再盗窃还可装入背包的最贵商品，以此类推。

8.3 集合覆盖问题

近似算法：在获得精确解需要的时间太长时，可使用近似算法
- 标准：速度有多快、得到的近似解与最优解的接近程度、
运行时间： O ( n 2 ) O(n^2) O(n2)

代码实现：

states_needed = set(["mt", "wa", "or", "id", "nv", "ut","ca", "az"])

stations = {}
stations["kone"] = set(["id", "nv", "ut"])
stations["ktwo"] = set(["wa", "id", "mt"])
stations["kthree"] = set(["or", "nv", "ca"])
stations["kfour"] = set(["nv", "ut"])
stations["kfive"] = set(["ca", "az"])
final_stations = set()

while states_needed:
    best_station = None
    states_covered = set()
    for station, states_for_station in stations.items():
        covered = states_needed & states_for_station
        if len(covered) > len(states_covered):
            best_station = station
            states_covered = covered
    
    final_stations.add(best_station)
    states_needed -= states_covered
    
print(final_stations)

运行时间：

精确算法	贪婪算法
O ( n ! ) O(n!) O(n!)	O ( n 2 ) O(n^2) O(n2)

8.4 旅行商问题

问题：要找出经由指定几个点的的最短路径——NP完全问题

九、K最近邻算法

9.1 创建推荐系统

特征抽取：毕达哥拉斯公式： ( a 1 ? a 2 ) 2 + ( b 1 ? b 2 ) 2 + ( c 1 ? c 2 ) 2 + ( d 1 ? d 2 ) 2 + ( e 1 ? e 2 ) 2 \sqrt{(a_1-a_2)^2+(b_1-b_2)^2+(c_1-c_2)^2+(d_1-d_2)^2+(e_1-e_2)^2} (a1??a2?)2+(b1??b2?)2+(c1??c2?)2+(d1??d2?)2+(e1??e2?)2 ?
分类：编组
回归：预测结果

9.2 机器学习

OCR（光学字符识别）
- 训练：浏览大量的数字图像，将这些数字的特征提取出来。
- 遇到新图像时，你提取该图像的特征，再找出它最近的邻居都是谁！
朴素贝叶斯分类器
预测股票市场

内容总结

以上是互联网集市为您收集整理的【算法图解】学习笔记全部内容，希望文章能够帮你解决【算法图解】学习笔记所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/603306.html

来源：【匿名】

【上一篇】关于寻找海王id的算法伪代码分析思路【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【【算法图解】学习笔记】教程文章相关的互联网学习教程文章

【算法学习笔记】76.DFS 回溯检测 SJTU OJ 1229 mine【代码】

扫雷玩得好还是有点好处的......这个题一开始像从后向前按照第一排的数字进行DFS 发现自己真傻,先不说这种情况下每个数字的填写情况很多, 还要处理相邻位置的问题。所以可以对每一位有没有地雷进行枚举。处理每一位的时候，要保证上一个数字是合理的，否则不用进行下去了，类似回溯，注意have变量的处理就好了。#include <iostream> #include <stack> usingnamespace std; //最长暗示dfs //遇到3 和 0 其实只有一种情况 //遇到2 和...

【视频编解码·学习笔记】7. 熵编码算法：基础知识 & 哈夫曼编码【代码】

一、熵编码概念：熵越大越混乱信息学中的熵：用于度量消息的平均信息量，和信息的不确定性越是随机的、前后不相关的信息，其熵越高信源编码定理：说明了香农熵越信源符号概率之间的关系信息的熵为信源无损编码后平均码长的下限任何的无损编码方法都不可能使编码后的平均码长小于香农熵，只能使其尽量接近熵与混乱程度：混乱度越高的信源，越难以被压缩，需要更大量的信息来表示其排列顺序熵编码基本思想：是使其前后的码字之间尽...

【算法学习笔记】85.破环为链序列DP 松弛+代价 SJTU OJ 1073 能量项链【代码】

和石子合并很像, 为了对环状进行处理, 我们可以把输入数据复制一份接连在后边. 这样在最后的结果枚举起点找最大即可.注意这里代价的计算, 因为我们的data[i]只记录了珠子的头珠子的尾部即是下一个珠子的头部.//因为计算dp[i][j]时需要用到dp[i][k] k比j小所以j顺序dp[k][j] k比i大所以i逆序 k插入即可for (int i = 2*n-1; i >=1 ; --i){for (int j = i; j <= 2*n; ++j){dp[i][j] = 0;for (int k = i; k < j ; ++k) dp[i][j] = ma...

【算法导论-学习笔记】以线性时间增长的排序——计数排序【代码】【图】

计数排序是一种能够达到运行时间能够线性时间θ(n)的排序算法。在排序算法里算是最快的算法之一，当然，他有很强烈的前提。下面开始介绍一下技术排序（Counting Sort）。算法思想计数排序假设n个输入元素中的每一个都是介于0到k之间的整数，此处k为某个整数。这样可以用一个数组C[0..k]来记录待排序数组里元素的数量。当k=O(n)时，计数排序的运行时间为θ(n).注：关于C[0..k]，用键值对描述的话，待排序元素是键，相同元素的个数是...

KMP算法学习笔记【代码】

KMP算法从零开始大部分来自他人博客，蒟蒻只是总结学习引言字符串匹配。给你两个字符串，寻找其中一个字符串是否包含另一个字符串，如果包含，返回包含的起始位置.char *str = "bacbababadababacambabacaddababacasdsd"; char *ptr = "ababaca";暴力解法如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符；如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被...

数据结构学习笔记模拟算法1【代码】

猜数字 #include<stdio.h> #include<time.h> int main() {int n,m,i=0;srand(time(NULL));n=rand()% 100 +1;do{printf("输入所猜的数字:");scanf("%d",&m);i++;if(m>n)printf("错误！所猜的数太大了!\n"); else if (m<n) printf("错误!所猜的数太小了！\n");}while (m!=n);printf("答对了!\n");printf("共猜测了%d次。\n",i) ;if(i<=5)printf("你太聪明了,这么快就猜出来了!");else if(i>5)printf("还需要改进方法，以便更快猜出...

数据结构与算法之美专栏学习笔记-复杂度分析【代码】

复杂度分析什么是复杂度分析数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”。因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。分别用时间复杂度和空间复杂度两个概念来描述性能问题，二者统称为复杂度。复杂度描述的是算法执行时间（或占用空间）与数据规模的增长关系。为什么要进行复杂度分析和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。掌握复杂...

STL学习笔记（算法概述）【代码】【图】

算法头文件要运用C++标准程序库的算法，首先必须包含头文件<algorithm>使用STL算法时，经常需要用到仿函数以及函数配接器。它们定义域<functional>头文件中。算法的分类可以按以下分类方式描述各个STL算法：非变动性算法(nonmodifying algorithms)变动性算法(modifying algorithms)移除性算法(removing algorithms)变序性算法(mutating algorithms)排序算法(sorting algorithms)已序区间算法(sorted range algorithms)数值算法(n...

【算法学习笔记】72.LCS 最大公公子序列动态规划 SJTU OJ 1065 小M的生物实验1【代码】

非常简单的DP如果dp[i,j]表示从0到i 和从0到j 这两段的相似度，那么可以知道每个dp[i,j]是由三种状态转化过来的第一种当dna1[i]==dna2[j]的时候 dp[i-1,j-1] + 1 长度加1第二种否则从下面两个状态过来那就是dp[i][j-1] 和 dp[i-1][j]//注意因为是顺序遍历这两个都已经计算过取两者最大即可。#include <iostream> #include <cstring> #include <algorithm> usingnamespace std;//最长公共子序列长度 LCS dpchar dna1[1000+1...

算法 - 最热教程

浅谈SQLServer查询优化器中的JOIN算法有没那种可逆算法是密文比明文短的呢？...javascript-类似Excel里面的NORMDIST函...C++中的分治算法及常见题目汇总压缩感知重构算法综述-学习笔记 c++中内置函数qsort（快速排序）和bsea...一、fpga图像处理算法整合基于遗传算法（deap）的非线性函数寻优...集成学习-Bagging集成学习算法随机森林...机器学习笔记（九）聚类算法及实践（K-...

首页 / 算法 / 【算法图解】学习笔记

【算法图解】学习笔记

内容导读

内容图文

一 、算法简介

1.1 二分查找

1.2 大O表示法

二、选择排序

2.1 数组与链表

2.2 选择排序

三、递归

四、快速排序

4.1 分而治之（D&C）

4.2 快速排序

4.3 再谈大O表示法

五、散列表

5.1 散列函数

5.2 散列表

5.3 装填因子

六、广度优先搜索

6.1 最短路径问题

6.2 广度优先搜索

七、狄克斯特拉算法

7.1 使用狄克斯特拉算法

7.2 术语

7.3 实现

八、贪婪算法

8.1 教室调度问题

8.2 背包问题

8.3 集合覆盖问题

8.4 旅行商问题

九、K最近邻算法

9.1 创建推荐系统

9.2 机器学习

内容总结

内容备注

内容手机端

【【算法图解】学习笔记】教程文章相关的互联网学习教程文章

算法 - 相关标签

算法 - 最新教程

算法 - 最热教程

一、算法简介