Long Long Ago


笔记: 算法图解:像小说一样有趣的算法入门书 (By Aditya Bhargava)

Yarco

  • Administrator
  • Jr. Member
  • *****
    • Posts: 56
    • View Profile
Code Path: https://github.com/egonschiele/grokking_algorithms

第1章 算法简介

...所以, 其实算法有相对应的数据结构(情况), 针对不同情况选择不同的算法.

1.2 二分查找

针对的是: 有次序的静态列表. 有次序意味着有大小, 意味着可基于大小进行排除.

1.3.4 一些常见的大 O 运行时间
O(log n), O(n), O(n log n), O(n^2), O(n!)
(有序性, 平行世界...)
像是降维:  低维度 <------ 线性世界 -------> 高维度

第2章 选择排序

2.2 数组和链表
数组: 针对现对固定的情况, +随机访问, +索引(关键字,下标关系)
链表: 删减频繁
(若以阴阳角度, 数组为阴, 链表为阳, 固化思维为阴, 跳跃思维为阳~)

2.3 选择排序
通常教选择排序会讲打牌这件事, 这里作者的例子是音乐播放次数的排序, 但我觉得另外一件事情可能更令人印象深刻.........择偶.

Mine with Numpy:
Code: [Select]
import numpy as np

arr = np.random.randint(10, size=10)

def findSmallest(arr):
    max = arr[0]
    idx = 0
    for i in range(1, len(arr)):
        if arr[i]<max:
            max = arr[i]
            idx = i
    return idx, max

findSmallest(arr)

## O(n)

print(arr)
def selectionSort(arr):
    ret = arr.copy()
    for i in range(0, len(ret)):
        idx, max = findSmallest(ret[i:])
        ret[i], ret[idx+i] = ret[idx+i], ret[i]
    return ret

print(selectionSort(arr))

书里的:
Code: [Select]
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])
« Last Edit: January 19, 2019, 04:12:48 pm by Yarco »


Yarco

  • Administrator
  • Jr. Member
  • *****
    • Posts: 56
    • View Profile
第3章 递归

* 基线条件
* 递归条件.

递归本身可以算一种循环, 只是借用了系统的栈做存储.

第4章 快速排序

4.1 分而治之

4.2 快速排序
Code: [Select]
def quicksort(arr):
    if len(arr) < 2:
        return arr
   
    pivot = arr[0]
    left = [i for i in arr[1:] if i < pivot]
    right = [i for i in arr[1:] if i >= pivot]
    ## O(2n)
    return quicksort(left) + [pivot] + quicksort(right)
## O(2n * log n)

print(arr)
print(quicksort(arr))

第5章 散列表

(也称为字典或字值对)

5.1 散列函数

5.2 应用
电话本, DNS, 防止重复, 缓存

5.3 冲突
5.4 性能
5.4.1 填装因子
(一旦超过0.7, 就需要重新分配)
5.4.2 良好的散列
均匀分布
Sha()
« Last Edit: February 10, 2019, 02:44:58 pm by Yarco »


Yarco

  • Administrator
  • Jr. Member
  • *****
    • Posts: 56
    • View Profile
第6章 广度优先搜索

(BFS, bread-first search)

6.1 图介绍

6.3 广度优先算法
1) 回答是否存在A->B的路径
2) 具体路径的条数

有向图
无向图

6.4 实现图

书中用dict来存储图, 但是是单向关系.

第7章 狄克斯特拉算法

加权图
非加权图

适用于:有向无环图

(... ...)
« Last Edit: February 11, 2019, 05:25:14 pm by Yarco »


Yarco

  • Administrator
  • Jr. Member
  • *****
    • Posts: 56
    • View Profile
第8章 贪婪算法

8.1 教室调度问题
8.2 背包问题

局部最优解 得到 全局最优解 的近似值.

8.4 NP 完全问题

Quote
元素较少时算法的运行速度非常快,但随着元素数量的增加,速度会变得非常慢。
涉及“所有组合”的问题通常是 NP 完全问题。
不能将问题分成小问题,必须考虑各种可能的情况。这可能是 NP 完全问题。
如果问题涉及序列(如旅行商问题中的城市序列)且难以解决,它可能就是 NP 完全问题。
如果问题涉及集合(如广播台集合)且难以解决,它可能就是 NP 完全问题。
如果问题可转换为集合覆盖问题或旅行商问题,那它肯定是NP完全问题。
(个人认为 指的是 当增加一个条件时, 将影响所有可能的已知答案 -- 点~全局 关联时, 是NP问题)

第9章 动态规划

(个人思考, 适合的情况属于)
* 近似的离散型数据/整型(子问题独立)
* 具有聚合值, 而根据这个聚合值判断优先

9.3 最长公共子串
9.3.4 最长公共子序列


Yarco

  • Administrator
  • Jr. Member
  • *****
    • Posts: 56
    • View Profile
第10章 K 最近邻算法

KNN

将需要分析的对象根据不同的特征值描述成对应的多维坐标轴上的位置, 在根据距离公式计算出距离.

(数据统计中的主成分分析?)

挑选特征值................需要强大的对人性的了解.

10.3 机器学习简介

10.3.1 OCR
10.3.2 创建垃圾邮件过滤器
10.3.3 预测股票市场

第11章 接下来如何做

11.1 树

(早就感觉二分查找和二叉查找树拥有类似的逻辑, 只是没有合适的语言去描述.  其实唯一的差别就是构造数据的情况, 如果已有排序的数据, 那么用2分查找; 如果数据本来就是在构造之中, 那么显然用 二叉查找树, 数据库大部分索引是它的增强型类型)

11.2 反向索引


11.3 傅里叶变换*
11.4 并行算法*
* 并行性管理开销
* 负载均衡
(有道理)

11.5 MapReduce
...

11.10 线性规划

(完)

很不错的书!!!