发门网
《趣学算法》读书笔记
创始人
2024-05-24 05:21:57
0次

内容摘要

主要介绍我对本书的一些自我感觉比较亮点地方的总结。

第一章

算法

  • 算法有两条线索，数据结构、算法策略。
  • 在这里插入图片描述
  • 在这里插入图片描述
  • 在这里插入图片描述
  • 在这里插入图片描述
  • 最坏情况对衡量算法的好坏具有实际意义。
  • 在这里插入图片描述

算法特性

在这里插入图片描述

时间复杂度

在这里插入图片描述

常见算法时间复杂度
  • 在这里插入图片描述
  • 在这里插入图片描述
时间复杂度的渐进上界

在这里插入图片描述

渐进精确界

用渐进上界和渐进下界逼近，在这里插入图片描述

空间复杂度

在这里插入图片描述

递归

  • 递归包括递推和回归。
  • 递推是将原问题不断分解成子问题，直到达到结束条件，返回最近子问题的解；然后逆向逐一回归，最终到达递推开始的原问题，返回原问题的解。

栈

后进先出。

数学知识

斐波那契数列

在这里插入图片描述

斐波那契数列和黄金分割比的关系：

在这里插入图片描述

第二章

贪心算法

在这里插入图片描述

贪心算法特性

贪心选择性质
  • 原问题的整体最优解可以通过一系列局部最优解的选择得到。
  • 原问题变为一个相似的但规模更小的子问题，而后的每一步都是当前最佳的选择。
  • 选择依赖于已做出的选择，但不依赖于未作出的选择。
  • 程序的运行过程中无回溯过程。
最优子结构性质

一个问题的最优解包含其子问题的最优解。

贪心算法案例

冒泡排序采用了贪心算法。

背包问题

在这里插入图片描述

创建栈

在这里插入图片描述

正态分布

大部分数据呈现正态分布，因此遍历是不合理的。

最小生成树

  • 权值最小的生成图。
  • 离散数学无向连通图相关知识。

避圈法

  • 在这里插入图片描述
  • 在这里插入图片描述

Kruskal算法和Prim算法

在这里插入图片描述

第三章

快速排序（sort）

快排原理

向左走、向右走，直到重合，重复此过程。

快排特点

  • 分解难，合并易。
  • 先难后易。
  • 原地排序。

排序复杂度

在这里插入图片描述

合并排序（归并排序）

合并排序特点

  • 分解容易，合并难。
  • 先易后难。
  • 需要辅助空间（辅助数组），异地排序。

排序算法效率

在这里插入图片描述

大整数乘法

  • 分治。
  • 乘法运算采用倒序保存结果。

时间复杂度

在这里插入图片描述

空间复杂度

在这里插入图片描述

四次乘法变三次乘法

在这里插入图片描述

时间复杂度变化

在这里插入图片描述

注意事项

在这里插入图片描述

第四章

动态规划

最优子结构

在这里插入图片描述

子问题重叠

在这里插入图片描述

如何使用动态规划

在这里插入图片描述
在这里插入图片描述

编辑距离

在这里插入图片描述

构造最优解

在这里插入图片描述

二叉搜索树

在这里插入图片描述

最优二叉搜索树

在这里插入图片描述

最优二叉树的最优值递归式（动态规划的查表法）

在这里插入图片描述

搜索成本（平均比较次数）

在这里插入图片描述

  • 关键字结点的搜索成本 在这里插入图片描述
  • 每个实结点的搜索成本=结点的深度*搜索概率。
  • 虚结点的搜索成本
  • 在这里插入图片描述
  • 每个虚结点的搜索成本=结点的深度*搜索概率。
搜索概率

在这里插入图片描述

第五章

回溯法

  • 在这里插入图片描述
  • List item

隐约束（剪枝函数）

  • 在这里插入图片描述
  • 在这里插入图片描述
约束函数和限界函数
  • List item
  • List item

时间复杂度

  • 在这里插入图片描述

n皇后

  • 以行为主导
  • 在这里插入图片描述
  • List item

最优加工顺序

在这里插入图片描述

贝尔曼规则

在这里插入图片描述

第六章

贪心策略对购物车问题的缺陷

在这里插入图片描述

队列

此类问题可以用队列（先近先出）解决

回溯法与分支限界法

在这里插入图片描述

第七章

线性规划

处理线性规划问题

在这里插入图片描述

单纯形表

特殊位置

在这里插入图片描述

  • 在这里插入图片描述
单纯形算法

将目标函数由非基本变量表示

最大网络流

在这里插入图片描述

可行流

  • 容量约束
  • 流量守恒

残余网络

在这里插入图片描述

附录F

四边不等式

在这里插入图片描述

本书免费访问路径

  1. https://gateway.pinata.cloud/ipfs/bafykbzaceauicbfg6xaw22pjmb7p75u4qrwiu77c4kgqwwy2gpwcvnr3v3ea4?filename=%E8%B6%A3%E5%AD%A6%E7%AE%97%E6%B3%95.pdf

  2. https://www.cnblogs.com/aerer/p/9931040.html

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：VirtualBox 虚拟机安装Windows10，珍藏版！！！

下一篇：APISpace 的 ChatGPT 它来了 一分钟快速接入没烦恼

相关内容

热门资讯

监控摄像头接入GB28181平... 流程简介将监控摄像头的视频在网站和APP中直播，要解决的几个问题是：1&...
【PdgCntEditor】解... 一、问题背景 大部分的图书对应的PDF，目录中的页码并非PDF中直接索引的页码...
在Word、WPS中插入AxM... 引言 我最近需要写一些文章，在排版时发现AxMath插入的公式竟然会导致行间距异常&#...
protocol buffer... 目录 目录 什么是protocol buffer 1.protobuf 1.1安装  1.2使用...
修复 爱普生 EPSON L4... L4151 L4153 L4156 L4158 L4163 L4165 L4166 L4168 L4...
Windows10添加群晖磁盘... 在使用群晖NAS时，我们需要通过本地映射的方式把NAS映射成本地的一块磁盘使用。 通过...
Fluent中创建监测点 1 概述某些仿真问题，需要创建监测点，用于获取空间定点的数据࿰...
ChatGPT 怎么用最新详细... ChatGPT 以其强大的信息整合和对话能力惊艳了全球，在自然语言处理上面表现出了惊人...
educoder数据结构与算法...                                                   ...
MySQL下载和安装（Wind... 前言：刚换了一台电脑，里面所有东西都需要重新配置，习惯了所...