当前位置:   article > 正文

图解算法_算法a1选择位于关键属性

算法a1选择位于关键属性

二、选择排序

2.1内存工作的原理

需要将数据存储到内存时,你请求计算机提供存储空间,计算机给你一个存储地址。需要存储多项数据时,有两种基本方式——数组和链表。

2.2数组和链表

2.2.1 链表

链表中的元素可存储在内存的任何地方。

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

链表的优势在于插入元素方面,需要同时读取所有元素时,链表的效率很高。

链表的缺点:在读取链表的最后一个元素时,你不能直接读取,因为你不知道他所处的地址,必须先访问元素1,然后元素2…直到访问最后一个元素。跳跃读取的话链表的效率就很低。

当需要在中间插入元素时,链表是更好地选择。

删除元素时链表也是更好地选择,因为只需修改前一个元素的指向地址就可以了,二使用数组时,删除元素后,必须将后面的元素都向前移。

通常我们都记录了链表的第一个元素和最后一个元素,因此删除这些元素时的运行时间为O(1)

2.2.2 数组

数组知道其中每个元素的地址。需要随机读取元素时,数组的效率很高,因为可以迅速找到数组中的任何元素。在链表中,元素并非靠在一起的,你无法迅速计算出第五个元素的内存地址,而必须先访问第一个元素以获得第二个元素的地址,在访问第二个元素以获得第三个元素的地址,以此类推,直到访问第五个元素。

通常情况下数组用的多,因为他支持随机访问。顺序访问:从第一个元素开始逐个的读取元素。链表只能顺序访问!随机访问意味着可以直接跳到要访问的元素上。所以支持随机访问的数组读取速度更快!

2.2.3 术语

数组的元素带编号,编号从0开始而不是从1开始,主要是从0开始觊觎数组的代码编写起来更容易,因此程序员始终坚持这样做。几乎所有的编程语言都从0开始对数组进行编号。

元素的位置称为索引,用索引表示位置。

2.2.4 删除

删除元素总能成功,因为是释放内存,如果没有足够的内存,插入操作可能失败,但任何情况下都能将元素删除。

选择排序

方法一、

# 选择排序

# 获取数组中的最小
import time


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):
    start = time.time()
    newArr = []
    for i in range(len(arr)):
        smallest = findSmallest(arr)
        newArr.append(arr.pop(smallest))
    end = time.time()
    print(f"find运行时间: {end - start}")
    return newArr
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

方法二、

def selectSort(arr):
    start = time.time()
    newArr = []
    newArr.append(min(arr))
    end = time.time()
    print(f"min运行时间: {end - start}")
    return newArr

arr = [i for i in range(999999)]
res2 = selectionSort(arr)[:9]
res1 = selectSort(arr)[:9]
print(res1, res2)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

在速度上方法一远远没有方法二快,但是可以做为初学的一种方式,我们知道min其实是一种迭代器,将数组中两个元素作对比。

小结

  • 计算机内存犹如一大堆抽屉。
  • 需要存储多个元素时,可使用数组或链表
  • 数组的元素都在一起
  • 链表的元素是分开的,其中每个元素都存储了下一个元素的地址。
  • 数组的读取速度很快
  • 链表的插入和删除速度很快
  • 在同一个数组中,所有元素的类型都必须相同(都为int、double等)。

三、递归

​ 如果使用循环,程序的性能可能更高;如果使用递归,程序可能更容易理解。如何选择要看什么对你来说更重要。

基线条件和递归条件

​ 由于递归函数调用自己,因此编写这样的函数容易出错,进而导致无限循环。所以编写递归时,必须告诉他何时停止递归。正因如此,每个地柜函数都有两部分:基线条件递归条件。递归条件指的是函数自己调用自己,而基线条件则指的是函数不在调用自己,从而避免无限循环。

For example

def add(i, result=0):
    result += i
    # print(result)
    if i <= 0:  # 基线条件
        return
    else:  # 递归条件
        return (add(i - 1, result=result))

add(88)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

调用栈

​ 栈是拥有插入和弹出操作的数据结构

​ 计算机在内部使用被称为调用栈的栈。我们来看看计算机是如何使用调用栈的。下面是一个简单地函数。

def greet2(name):
    print(f"how are you {name}?")


def bye():
    print("ok bye!")


def greet(name):
    print(f"hello {name}!")
    greet2(name)
    print("nice to meet you!")
    bye()
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

我们知道每次定义一个函数,都会在内存中生成一个名称空间,每调用一次函数都会执行里面的代码,函数里调用涉及的所有变量的值存储到内存中。我们运行greet(superme),打印hello superme,再调用greet2(superme)。同样,计算机也为这个函数调用分配了一块内存。

​ 计算机使用一个栈来表示这些内存块,其中第二个内存块位于第一个内存块上面(greet2(superme)greet(superme)上面),当greet2(superme)运行完毕(调用返回

),此时栈顶的内存被弹出。

​ 现在栈顶的内存是greet(superme),此时greet(superme)函数还未运行完毕,还在栈底(第一个栈),然后运行nice to meet you,执行bye函数,栈顶加载bye的内存块。最终运行完bye,返回到greet函数,完成整个函数的返回。这个栈用于存储多个函数的变量,称为调用栈

递归调用栈

递归函数也使用调用栈,下面是计算阶乘的递归函数

def fact(x):
    if x == 1:
        return 1
    else:
        return x * fact(x - 1)


result = fact(3)
print(result)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

下面详细分析调用fact(3)时调用栈是如何变化的。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ygZtXSGU-1598689218201)(C:%5CUsers%5CS%5CAppData%5CRoaming%5CTypora%5Ctypora-user-images%5Cimage-20200815230406416.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IYvNybSp-1598689218204)(C:%5CUsers%5CS%5CAppData%5CRoaming%5CTypora%5Ctypora-user-images%5Cimage-20200815230511472.png)]

注意每个fact调用都有自己的x变量。在一个函数调用不能访问另一个的x变量。

栈在递归中扮演着重要的角色。

小结:

  • 递归是指的自己调用自己的函数
  • 每个递归函数都有两个条件:基线条件和递归条件
  • 栈有两种操作:压入和弹出。
  • 所有函数调用都进入调用栈。
  • 调用栈可能很长,这将占用大量的内存。

快速排序

分而治之

1)找出基线条件,这种条件必须尽可能简单。

2)不断将问题分解(或者说缩小规模),知道符合基线条件。

分而治之并非可用于解决问题的算法,而是一种解决问题的思路。

对于排序算法来说不用排序的数组就是最简单的数组,因此基线条件为数组为空或者只包含一个元素的(len(arr)<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)  # 数组的拼接
    
# 感觉并不快 还是要遍历整个数组
array = [1, 23, 45453, 4, 34, 523, 23, 4, 234, 23, 42, 34, 23, 423, 4, 235, 2, 35, 23, 523, 52, ]
result = quicksort(array)
print(result)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

平均情况和最糟糕情况

最佳情况

每次都能分到两个相同长度的数组 时间复杂度 O(logn)

平均情况

每次都能分割到两个数组 时间复杂度 nO(logn)

糟糕情况

列表原本有序,只能得到一个数组相当于遍历 时间复杂度O(n)

小结

  • 分而治之将问题逐步分解。使用分而治之处理列表时,基线条件很可能是空数组或只包含一个元素的数组。
  • 实现快速排序时,请随机的选择做基准值的元素。快速排序的平均运行时间为nO(logn)。
  • 大O表示法中的常量有时候事关重大,这就是快速排序比合并排序快的原因。
  • 比较简单查找和二分法查找时,常量几乎无关紧要,因为列表很长时,O(logn)要比O(n)快得多。

散列表

最有用的数据结构之一

散列函数

散列函数是这样的函数,即无论你给它什么数据,他都还你一个数字。(看起来像字典)

如果用专业术语来表达的话,我们会说,散列函数“将输入映射到数字”。你可能认为散列函数输出的数字没什么规律,但其实散列函数必须满足一些要求。

  • 他必须是一致的。例如,假设你输入apple时得到的是4,name每次输入apple时,得到的都必须为4.如果不这样,散列表将毫无用处。
  • 它应将不同的输入映射到不同的数字。例如如果散列函数不管输入什么都返回1,他就不是一个好的散列函数。最理想的情况是,将不同的输入映射到不同的数字。

散列函数准确的指出了价格的存储位置,你根本不用查找!原因如下

  • 散列函数总是将同样的输入映射到相同的索引。每次你输入一个 avocado ,得到的都是同一个数字。因此,你可首先使用它来确定将鳄梨的价格存储在什么地方,并在以后使用它来确定鳄梨的价格存储在什么地方。
  • 散列函数将不同的输入映射到不同的索引。avocado映射到索引4,milk映射到索引0.每种商品都映射到数组的不同位置,让你能够将其价格存储到这里。
  • 散列函数知道数组有多大,只返回有效的索引。如果数组包含了5个元素,散列函数就不会返回无效索引100.

​ 在我们学习的复杂数据结构中,散列表可能是最有用的,也被称为散列映射、映射、字典和关联数组。散列表的速度很快!

python提供的散列表实现为字典,你可使用函数dict来创建散列表。

小结:

​ 你几乎根本不用自己去实现散列表,因为你使用的编程语言提供了散列表的实现。你可使用python给你提供的散列表,并假定能够获得平均情况下的性能:常量时间。

​ 散列表是一种功能强大的数据结构,期操作速度快,还能让你以不同的方式建立数据模型。你可能很快会发现自己经常在使用它。

  • 你可以结合散列函数和数组来创建爱你散列表
  • 冲突很糟糕,你应该使用可以最大限度减少冲突的的散列函数
  • 散列表的查找、插入和删除速度都非常快
  • 散列表适合用于模拟映射关系
  • 一旦填装因子超过0.7 ,就应该调整散列表的长度。
  • 散列表可用于缓存数据(例如,在web服务器上)。
  • 散列表非常使用用于防止重复。

广度优先搜索

​ 本章将介绍图。首先,我将说说什么是图(他们不涉及X和Y轴),再介绍第一种图算法——广度优先搜索

​ 广度优先搜索让你能够找出两样东西之间的最短距离,不过最短距离的含义有很多!使用广度优先搜索可以:

  • 编写国际跳棋AI,计算最少走多少部就可以获胜

  • 编写拼写检查器,计算最少编辑多少个地方就可以将拼错的单词改成正确的单词,如将READED改为READER只需要编辑一个地方:

  • 根据你的人际关系网络找到关系最近的医生。

    在我所知道的算法中,图算法应该是最有用的。

图是什么

图模拟一组连接。图由节点和边组成。一个节点可能与众多节点直接相连,这些节点被称为邻居。

树:

树是一种特殊的图,其中没有往后指的边。

广度优先搜索

  • 第一类问题:从节点A出发,有前往节点B的路径吗?
  • 第二类问题:从节点A出发,前往节点B的那条路径最短?

列队

列队只支持两种操作:入队和出队。

​ 如果你将两个元素加入队列,先加入的元素将在后加入的元素之前出队。因此,你可以使用队列来表示查找名单!这样,先加入的人将先出队并先被检查。

队列是一种先进先出的数据结构,而是一种后进先出的数据结构

小结

  • 广度优先搜索支出是否有从A到B的路径
  • 如果有,广度优先将找出最短路径。
  • 面临类似寻找最短路径问题时,可尝试使用图来建立模型,再使用广度优先搜索来解决问题。
  • 有向图中的边为箭头,箭头的方向指定了关系的方向,例如,rama---->adit表示rama欠adit钱。
  • 无向图中的边不太箭头,其中的关系是双向的,例如:ross—rache表示“ross和rache约会,而rachel也与ross约会”。
  • 队列是先进先出(FIFO)的
  • 栈是后进先出(LIFO)的
  • 你需要按加入顺序检查搜索列表中的人,负责找的就不是最短路径,因此搜索列表必须是队列。
  • 对于检查过的人,务必不要再去检查,否则可能导致无限循环。(判断是否在列表)

迪克斯特拉算法

  1. 找出“最便宜”的节点,即可在最短时间内到达的节点。
  2. 更新该节点的邻居的开销,
  3. 重复这个过程,直到对图中的每个节点都这样做了
  4. 计算最终路径。

迪克斯拉特算法用于每条边都有关联数字的图,这些数字称为权重(weight)。

带权重的图称为加权图,不带权重的图称为非加权图

​ 要计算非加权图中的最短路径可以使用广度优先算法,计算加权图中的最短路径,意义使用迪克斯特拉算法(图还可能有

​ 无向图就是 , 无向图汇总每条边都是一个环。迪克斯特拉算法只适用于有向无环图

迪克斯特拉算法关键理念,找到最优秀的解决方案,并确保没有比这个更好地解决方案。

负权边

如果有负权边,就不能使用迪克斯特拉算法。

小结:

  • 广度优先搜索用于在非加权图中查找最短路径
  • 迪克斯特拉算法用于在加权图中查找最短路径
  • 仅当权重为正是迪克斯特拉算法才管用
  • 如果途中包含负权边,请使用贝尔曼——负的算法

贪婪算法

NP完全问题的简单定义是,以难解著称的问题,如旅行商问题和集合覆盖问题很多非常聪明的人都认为,根本不可能编写出快速解决这些问题的算法。

什么是NP完全问题:

  • 元素较少时算法的运行速度非常快,但随着元素数量的增加,速度会变得非常慢。
  • 涉及“所有组合”的问题通常是NP完全问题
  • 不能将问题分成小问题,必须考虑各种可能的情况。这可能是NP完全问题
  • 如果涉及序列(如旅行商问题中的城市序列)且难以解决,他可能就是NP完全问题
  • 如果问题涉及集合(如广播台集合)且难以解决,他可能是NP完全问题
  • 如果问题可转换为集合覆盖问题或旅行商问题,那她肯定是NP完全问题。

动态规划

背包问题

K最邻近算法

毕达哥拉斯定理

余弦相似度

朴素贝叶斯分类器

小结:

  • KNN用于分类和回归,需要考虑最近的邻居。
  • 分类就是编组
  • 回归就是预测结果(如数字)。
  • 特征抽取意味着将物品(如水果活用户)转换为一系列可比较的数字
  • 能否挑选合适的特征 关乎KNN算法的成败。

Another

在庞大数组中查找,最快的方法是二分查找,常用于注册

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hIYodZMa-1598689218205)(C:%5CUsers%5CS%5CAppData%5CRoaming%5CTypora%5Ctypora-user-images%5Cimage-20200823162059293.png)]

反向索引

一个散列表。将单词映射到包含它的页面。常用于创建搜索引擎。

傅里叶变换

绝妙优雅且应用广泛的算法少之又少,傅里叶变换算是一个。傅里叶变换就相当于,你给它一杯冰沙,它能告诉你其中包含哪些成分。

傅里叶变换科创就爱你类似于shazam这样的音乐识别软件。傅里叶变换的用途及其广泛,遇到他的可能性极高!

并行算法

分布式算法

映射函数和归并函数

映射函数:

归并函数:

布隆过滤器和HyperLogLog

布隆过滤器是一种概率型数据结构,他提供的答案有可能不对,但很有可能是正确的

布隆过滤器非常适合适用于不要求答案绝对准确的情况

HyperLogLog是一种类似于布隆过滤器的算法。

SHA算法

局部敏感的散列算法

Diffie-Hellman密匙交换

  • 双方无需知道加密算法。他们不必会面协商要使用的加密算法。
  • 要破解加密的消息比登天还难

Diffie-Hellman算法及其代替者RAS依然被广泛使用

擎。

傅里叶变换

绝妙优雅且应用广泛的算法少之又少,傅里叶变换算是一个。傅里叶变换就相当于,你给它一杯冰沙,它能告诉你其中包含哪些成分。

傅里叶变换科创就爱你类似于shazam这样的音乐识别软件。傅里叶变换的用途及其广泛,遇到他的可能性极高!

并行算法

分布式算法

映射函数和归并函数

映射函数:

归并函数:

布隆过滤器和HyperLogLog

布隆过滤器是一种概率型数据结构,他提供的答案有可能不对,但很有可能是正确的

布隆过滤器非常适合适用于不要求答案绝对准确的情况

HyperLogLog是一种类似于布隆过滤器的算法。

SHA算法

局部敏感的散列算法

Diffie-Hellman密匙交换

  • 双方无需知道加密算法。他们不必会面协商要使用的加密算法。
  • 要破解加密的消息比登天还难

Diffie-Hellman算法及其代替者RAS依然被广泛使用

线性规划

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/代码探险家/article/detail/1006213
推荐阅读
相关标签
  

闽ICP备14008679号