标签：函数 元素 list 笔记 列表 算法 数组

初心：最开始出发的原因

• 论文的代码复现也就是算法及其实现，需要精通算法
  • 学习完算法的基础知识，大致了解什么是算法以及有哪些算法

目标拆分

采用28法则分析事物的本质，找到20%的核心部分，但不是只学20%的部分，而是在系统学习中更加注重那20%

• 学会十大算法的原理及其python实现
  • [ ]

阶段性目标

DEADLINE

TOPICs	DDL	FINISHED

RETROSPECTIVE REVISION TIMETABLE

颜色表学习情况：红色->黄色->绿色

TOPICs	ROUND 1	ROUND 2	ROUND 3
CH1 算法简介	7.20黄
CH2 选择排序
CH3 递归
CH4 快速排序	7.20黄
CH5 散列表	7.20红
CH6 广度优先搜索	7.20红
CH7 狄克斯特拉算法
CH8 贪婪算法
CH9 动态规划
CH10 K最近邻算法
CH11 接下来如何做

PROGRESS

• CH1 算法简介
• CH2 选择排序
• CH3 递归
• CH4 快速排序
• CH5 散列表
• CH6 广度优先搜索
• CH7 狄克斯特拉算法
• CH8 贪婪算法
• CH9 动态规划
• CH10 K最近邻算法
• CH11 接下来如何做

近期TODOs

• 7月：一天1H算法，能看多少看多少

复盘

1

• 问题：

• 原因：

• 解决：
  • 3/5->
• 反馈：

算法图解

是一本入门级的读物，由浅入深地讲述了很多基础的概念，从激发读者兴趣的角度来看，作者无疑是很成功的。将入门的难度拉低，从而使读者能够从中在获得知识的同时感受到快乐。既然是入门级读物，那么也必然存在深度不足的问题，需要读者另外进行补充学习。……未完待续

目录

摘抄目录的原因是为了方便之后的复习，可以提供一些思路；
⭐表示重点和掌握不好的部分；
内容中的加粗表示知识点的欠缺，需要重点补漏！！！

CH1 算法简介

在本章中，你学习了：

• 二分查找的速度比简单查找快得多
• O(log n)比O(n)快。需要搜索的元素越多，前者比后者就快得越多。
• 算法运行时间并不以秒为单位。
• 算法运行时间是从其增速的角度度量的。
• 算法运行时间用大O表示法表示。
  ①简单查找->二分查找；②大O表示法：定义、常见；

• 引言：算法是一组完成任务的指令，任何代码片段都可视为算法
  • 性能方面：不了解算法的优缺点，算法的实现毫无用处
  • 问题解决技巧：学习最为广泛的算法，从而学习更具体的其他算法
• ⭐二分查找：问题是在有序列表中找到目标元素并反馈其位置，即输入是n维有序的元素列表，如果要查找的元素在其中，则返回其位置；否则返回null。
  • 更佳的查找方式：
    • 简单查找：从第一个元素开始一个个比较、排除；最多需要n步；
    • 二分查找：用中间元素进行比较，换区间再比较，每次排除一半元素；最多需要\(log_2 n\)步；
  • 运行时间：选择效率最高的算法，以最大限度地减少运行时间或占用空间；
    • 线性时间：简单查找；最多处理次数和列表长度n相同
    • 对数时间：二分查找；最多处理次数是列表长度的对数
  • 问题：判断有序数组中是否存在一个值，若存在则返回其位置，若不存在则返回None，若存在则返回索引。
  • 原理：定义binary_search函数，定义low和high作为查找的区间，当区间不存在时，直接返回None；当区间存在时，比较中间元素和数的大小，如果大了或小了则调整区间，如果正好相等则返回索引。
  • python实现：

def binary_search(list, item):  
    # 传入的有序列表list  
    # 传入要查找的目标值item  
    low = 0  # low和high用于跟踪要查找的列表区间  
    high = len(list) - 1  # 最大数的下标  
    while low <= high:      # 只要范围没有缩小到只包含一个元素  
        mid = (low + high) // 2  # 只检查中间的元素  
        if list[mid] == item:   # 找到了元素  
            return mid  
        if list[mid] > item:    # 猜的数字大了  
            high = mid - 1      # 在mid左半边找  
        else:       # 猜的数字小了  
            low = mid + 1  # 在mid右半边找  
    return None     # 没有找到指定的元素  
  
  
my_list = [1, 3, 5, 7, 9]  
binary_search(my_list, 3)  # => 1  
binary_search(my_list, -1)  # => None

• 大O表示法：用于表示算法的速度(运行时间随着列表/输入增长的速度)
  • 算法的运行时间以不同的速度增加：简单查找\(O(n)\)；二分查找\(O(log_2 n)\)；
  • 理解不同的大O运行时间
  • 大O表示法指出了最糟情况下的运行时间
  • 一些常见的大O运行时间：
    • \(O(log_2 n)\)：对数时间；二分查找
    • \(O(n)\)：线性时间；简单查找
    • \(O(n*log_2 n)\)：快速排序
    • \(O(n^2)\)：选择排序
    • \(O(n!)\)：旅行商问题
  • 旅行商：旅行商要去n个城市，确保旅程最短，操作数为\(A^{n-1}_n(A!)\)，运行时间为\(O(n!)\)

CH2 选择排序

在本章中，你学习了：

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

• 内存的工作原理：
  • 计算机类似于抽屉的集合体，每个抽屉都有地址
  • 要存1个数据时，计算机分配一个存储地址；要存储多项数据时，有链表和数组两个基本方式
• 数组和链表
  • 链表：
  • 数组
  • 术语
  • 在中间插入
  • 删除
• ⭐选择排序：
  • 问题：对一个无序数组按从小到大的顺序进行排序，从而获得有序数组。
  • 原理：定义findSmallest函数，假设数组一个值是最小的，遍历列表中所有元素，比较与最小值的大小，如果小的话则返回其索引；定义selectionSort函数，遍历列表中所有元素，找到当前列表的最小元素索引，将最小元素放入新数组中，并从旧数组中移除。
  • python实现：

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])

• 补充学习：
  • 列表list与数组array的定义：^[1]
    • 列表是由一系列按特定顺序排列的元素组成，可以将任何东西加入列表中，其中的元素之间没有任何关系；Python中的列表(list)用于顺序存储结构。它可以方便、高效的的添加删除元素，并且列表中的元素可以是多种类型。
    • 数组也就是一个同一类型的数据的有限集合。
  • 相同点：都可以根据索引来取其中的元素；
  • 不同点：
    • 列表list中的元素的数据类型可以不一样。数组array里的元素的数据类型必须一样；
    • 列表list不可以进行数学四则运算，数组array可以进行数学四则运算；
    • 相对于array，列表会使用更多的存储空间。
    • 由于list与array的不同，所以也会涉及到Python里range()函数和numpy里的numpy.arange()的用处不同。

import numpy as np
lis1=[1,2,3,4]  #lis1是列表类型
a = np.array([1,2,3,4])  #a是数组类型
#从下面print可以看出 list和array都可以根据索引来操作；
print("list",lis1,lis1[0],'\n','array',a,a[0])#运行结果：list [1, 2, 3, 4] 1  \n array [1 2 3 4] 1
#从下面print可以看出list的+法运算是列表长度的增删，与数学计算无关；
#而array的＋法运算是真正的数学四则运算；lis1
print("list+list",lis1+,'\n','array+array',a+a)#运行结果：list+list [1, 2, 3, 4, 1, 2, 3, 4]  \n  array+array [2 4 6 8]

CH3 递归

在本章中，你学习了：

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

• 递归：递归函数自己调用自己

def look_for_key(box):
	for item in box:
		if item.is_a_box():
			look_for_key(item)  # 递归
		elif item.is_a_key():
			print "found the key!"

• 基线条件和递归条件：
  • 基线条件：告诉它何时停止递归，避免无限循环；函数不再调用自己的条件；用if语句表示；
  • 递归条件：函数调用自己的条件；用else表示；
  • ⭐python实现：

def countdown(i):  
  print i  
  if i <= 0:    # base case基线条件  
    return  
  else:   # recursive case递归条件  
    countdown(i-1)  
  
countdown(5)

• 栈stack：一种仅支持压入(插入)和弹出(删除并读取)的数据结构
  • 调用栈call stack：计算机在内部使用被称为调用栈的栈；
    • 函数调用另一函数时，先保护现场(申请的内存并没有释放，还保留着)，再开辟新的现场。
    • greet调用greet2函数时，greet函数暂停执行，变量被保存在内存中，继而执行greet2函数，从栈顶压入(在greet上堆积木)，greet2函数执行完毕后，栈顶内存被弹出(推掉greet上积木)，greet2函数结束，变量也消失了，继续执行greet函数。
    • 递归如果没有结束条件，函数所有的变量值会保存在内存中，不主动释放内存的话，会造成stackoverError。
    • python实现：

def greet2(name):  
    print "how are you, " + name + "?"  
  
def bye():  
    print "ok bye!"  
  
def greet(name):  
    print "hello, " + name + "!"  
    greet2(name)  
    print "getting ready to say bye..."  
    bye()  
  
greet("adit")

• (2级)递归调用栈：递归函数也使用调用栈
  • 理解：
  • ⭐python实现：阶乘factorial

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

• 补充学习：
  • 调用栈是解释器（比如浏览器中的JavaScript解释器）追踪函数执行流的一种机制。当执行环境中调用了多个函数时，通过这种机制，我们能够追踪到哪个函数正在执行，执行的函数体中又调用了哪个函数。每调用一个函数，解释器就会把该函数添加进调用栈并开始执行。

CH4 快速排序

在本章中，你学习了：

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

• 分而治之divide and conquer, D&C：递归式问题的解决方法；将难以解决的问题不断拆分，直到清晰易懂；现实中就是将一件难的事情不断拆分到最小单位，然后一一解决。
  • 步骤：
    • 找出简单的基线条件：数组的递归函数，基线条件通常是数组为空或只包含一个元素。
    • 确定如何缩小问题的规模，使其符合基线条件
  • 问题：分别使用循环和递归的方法计算一个数组中的元素之和
  • 原理： 定义sum函数，……
  • python实现：

# 循环
def sum(arr):  
  total = 0  
  for x in arr:  
    total += x  
  return total  
  
print sum([1, 2, 3, 4])

# 递归
def sum(list):  
  if list == []:  
    return 0  
  return list[0] + sum(list[1:])

• ⭐快速排序：递归+D&C
  • 问题：已知一个无序数组，对数组进行排序。
  • 原理：定义quicksort函数，如果数组数目小于等于1则无需排序，如果数组数目大于1则需要排序，将第一个元素作为基准值，将所有小于基准值的元素放在左边less数组中，将所有大于基准值的元素放在右边greater数组中，对less数组和greater数组进行递归调用，将基准值和它们组合在一起返回。
  • python实现：

def quicksort(array):  
    if len(array) < 2:  # base case基线条件：为空或只包含一个元素的数组是有序的  
        return array  
    else:  # recursive case递归条件  
        pivot = array[0]  # 将第一个元素作为基准值pivot  
        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]))

• 再谈大O表示法
• 补充学习：
  • 分而治之是在分解大问题为小问题后分别求解所有小问题；减而治之是在分解大问题为小问题后求解某个小问题

CH5 散列表

在本章中，你学习了：你可以结合散列函数和数组来创建散列表。冲突很糟糕，你应使用可以最大限度减少冲突的散列函数。散列表的查找、插入和删除速度都非常快。一旦装填因子超过0.7，就该调整散列表的长度。散列表可用于缓存数据（例如在web服务器上）。散列表非常适合用于防止重复。

• 散列函数：任何输入都可以映射到数字(数组的索引值)
  • 要求：输入和输出必须一一对应；不同的输入映射到不同的数字(×)。
  • 散列表hash table：结合散列函数和数组，使用散列函数来确定元素在数组中的存储位置；又名散列映射、映射、字典和关联数组；python提供的散列表实现为字典(将键映射到值)，用dict()创建散列表。
• 应用案例：
  • 将散列表用于查找：访问网址时，网站会映射/转换为IP地址，如google.com->74.125.239.133，此过程为DNS解析resolution
  • 防止重复：使用散列表检查重复，速度非常快
    • 问题：管理一个投票站，一人只能投一票，通过对比名字和名单防止重复投票
    • 方法：定义check_voter函数。如果散列表中存在名字，则提醒；如果散列表中不存在民泽，则将名字加入散列表。
    • python实现：

voted = {}  # 散列表()用于记录已投票的人  
def check_voter(name):  
  if voted.get(name):   # voted中存在name，则get()返回它的值True  
    print("kick them out!")  else:     # voted不存在name，则在字典中记录  
    voted[name] = True
    print("let them vote!")  
check_voter("tom")  
check_voter("mike")  
check_voter("mike")

- 将散列表用作缓存(将数据记住而不再重新计算)

• 冲突：给两个键分配的位置相同时发生冲突，在数组的这个位置存储一个链表
• 性能：
  • 较低的装填因子：装填因子=散列表包含的元素数÷位置总数；装填因子大于0.7，就调整散列表的长度。
  • 良好的散列函数：结果均匀分布，映射范围尽可能大。
• 补充学习：
  • 散列函数就是hash函数，hashMap和Hash Table都是hash函数的具体应用。

CH6 广度优先搜索

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

• 图简介：
  • 最短路径问题：前往某地的最短路径，把对方将死的最少步数。
    • 步骤：使用图来建立问题模型；使用广度优先搜索解决最短路径问题。
• 图是什么：
  • 由节点node和边edge组成；一个节点可能与众多节点直接相连，这些节点被称为邻居。
  • 用于模拟不同的东西是如何相连的
• 广度优先搜索：
  • 查找最短路径：执行过程中，搜索范围从起点开始逐渐向外延伸，即先检查一度关系，再检查二度关系。->使用队列queue，按添加顺序进行检查
  • 队列：类似于栈，不能随机地访问队列中的元素，仅支持入队和出队。栈是后进先出(Last In First Out, LIFO)，队列是先进先出(First In First Out, FIFO)。
• 实现图：
  • 散列表将键映射到值，将节点映射到其所有邻居。
• 问题：
• 方法：
• python实现：

CH7 狄克斯特拉算法

在本章中，你学习了：广度优先搜索用于在非加权图中查找最短路径。狄克斯特拉算法用于在加权图中查找最短路径。仅当权重为正时狄克斯特拉算法才管用。如果图中包含负权边，请使用贝尔曼-福德算法。

• 使用狄克斯特拉算法：
  • 找出最便宜的节点，即可在最短时间内到达的节点。
  • 对于该节点的邻居，检查是否有前往它们的最短路径，如果有，就更新其开销。
  • 重复这个过程，直到对图中的每个节点都这样做了。
  • 计算最终路径。
• 术语
  • 权重：图的每条边都有关联数字
  • 加权图：带权重的图，用狄克斯特拉算法计算最短路径；非加权图：不带权重的图，用广度优先搜索计算最短路径。
  • 无向图：两个节点彼此指向对方，即环。
• 换钢琴：
  • 计算最终路径，还需要在表中添加表示父节点的列；沿着父节点回溯，便得到了完整的交换路径。
  • 最短路径不一定是物理距离，也可能是使某种度量指标最小。
• 负权边：
  • 不能使用狄克斯特拉算法，改用贝尔曼-福德算法
• python实现：

CH8 贪婪算法

在本章中，你学习了：贪婪算法寻找局部最优解，企图以这种方式获得全局最优解；对于NP完全问题，还没有找到快速解决方案；面临NP完全问题时，最佳的做法是使用近似算法；贪婪算法易于实现、运行速度快，是不错的近似算法。

• 教室调度问题
• 背包问题
• 集合覆盖问题

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 in stations.items():  
    covered = states_needed & states  
    if len(covered) > len(states_covered):  
      best_station = station  
      states_covered = covered  
  
  states_needed -= states_covered  
  final_stations.add(best_station)  
  
print final_stations

• NP完全问题
  • 旅行商问题详解
  • 如何识别NP完全问题

CH9 动态规划

在本章中，你学习了：需要在给定约束条件下优化某种指标时，动态规划很有用；问题可分解为离散子问题时，可使用动态规划来解决；每种动态规划解决方案都涉及网格；单元格中的值通常就是你要优化的值；每个单元格都是一个子问题，因此你需要考虑如何将问题分解为子问题；没有放之四海而皆准的计算动态规划解决方案的公式。

• 背包问题
  • 简单算法：尝试各种可能的组合，并找出价值最高的组合。
  • 动态规划：从小问题着手，逐步解决大问题。
• 背包问题FAQ
  • 再增加一件商品将如何呢：每次迭代时，都存储当前的最大价值。
  • 行的排列顺序发生变化时结果将如何：没有变化。
  • 可以逐列而不是逐行填充网格吗：没有变化
  • 增加一件更小的商品将如何呢：需要考虑的粒度更细，因此必须调整网格
  • 可以偷商品的一部分吗
  • 旅游行程最优化
  • 处理相互依赖的情况
  • 计算最终的解时会涉及两个以上的子背包吗
  • 最优解可能导致背包没装满吗
• 最长公共子串
  • 绘制网格
  • 填充网格
  • 揭晓答案
  • 最长公共子序列
  • 最长公共子序列之解决方案

if word_a[i] == word_b[j]:  
  # The letters match.  
  cell[i][j] = cell[i-1][j-1] + 1  
else:  
  # The letters don't match.  
  cell[i][j] = max(cell[i-1][j], cell[i][j-1])

CH10 K最近邻算法

在本章中，你学习了：HNN用于分类和回归，需要考虑最近的邻居。分类就是编组。回归就是预测结果(如数字)。特征抽取意味着将物品(如水果或用户)转换为一系列课比较的数字。能否挑选合适的特征事关KNN算法的成败。

• 橙子还是柚子
• 创建推荐系统
  • 特征提取：特征转为一组k维的数字
  • 回归：预测结果，如一个数字
  • 挑选合适的特征：
• 机器学习简介：
  • 光学字符识别OCR：
  • 创建垃圾邮件过滤器
  • 预测股票市场

CH11 接下来如何做

在本章中，你学习了：

• 树
• 反向索引
• 傅里叶变换
• 并行算法
• MapReduce
  • 分布式算法为何很有用
  • 映射函数
  • 归并函数
• 布隆过滤器和HyperLogLog
  • 布隆过滤器
  • HyperLogLog
• SHA算法
  • 比较文件
  • 检查密码
• 局部敏感的散列算法
• Diffie-Hellman密钥交换
• 线性规划

---

1. https://blog.csdn.net/woshisunyizhen/article/details/105101083 ↩︎

标签：函数,元素,list,笔记,列表,算法,数组
From： https://www.cnblogs.com/ouu2022/p/17089795.html