Data_Structures_and_Algorithms_in_Dart

一个包含 Dart 中数据结构和算法实现的存储库。

什么是算法？

f: I => O

算法被定义为一个将任意大小的输入映射到固定大小输出的函数。该函数可以是一个步骤，也可以是一系列步骤。它可以只执行一次，也可以在迭代或递归下执行。

算法必须是——

  1. 正确的
  2. 高效的

正确性——

算法的正确性通过归纳法来定义。它遵循以下步骤——

  1. 基本情况——我们检查算法在可能的最少输入数，即 1 个输入下的情况。
  2. 假设——我们假设算法将适用于随机输入数 n。
  3. 归纳步骤——我们检查算法在输入 n+1 时的正确性。

既然我们已经证明了算法的正确性，那么让我们来讨论效率。

效率——

效率定义了算法运行的速度以及相对于所有其他可能方法的运行速度。在数学上，我们假设所有处理器具有相同的处理能力，并期望效率取决于输入的大小。如果我们将其绘制在图上，它将是 y 轴上的一个值（作为因变量），它取决于输入的大小（在 x 轴上）。

我们有一些函数可以将算法的输入大小与其性能关联起来。

  1. 常数时间 – O(c)
  2. 线性时间 – O(n)
  3. 对数时间 – O(log(n))
  4. 对数线性时间 – O(n * log(n))
  5. 二次时间 – O(n^2)
  6. 多项式时间 – O(n^c)
  7. 指数时间 – 2^(O(n))

effeciency graph

数据结构——

为了理解数据结构，我们首先需要理解我们当前的计算模型——

我们过去使用的是 32 位 CPU（处理器），这只允许 2^32 即 4GB 的 RAM（内存）。技术发展到现在，我们有了 64 位系统，它允许 2^64 即 20 EB 的内存。但 CPU 的字长仍然很小，即 64 位。它们可以执行——

  1. 二进制运算
  2. 算术运算
  3. 位运算
  4. 内存读写

但是，如果我们想对大于 64 位的数据执行任何操作怎么办？

这就是我们需要的数据结构！

数据结构用于操作大量数据。有两种方法可以存储非恒定数量的数据，以便更快地执行对这些信息的操纵——

  1. 将问题简化为您已知的结构。
  2. 设计您自己的递归算法。

以下是属于这些方法下的主题——

1. 将问题简化为您已知的内容——

搜索问题——

  1. 静态数组
  2. 链表
  3. 动态数组
  4. 排序数组
  5. 直接访问数组
  6. 哈希表
  7. 平衡二叉树
  8. 二叉堆

排序算法——

  1. 插入排序
  2. 选择排序
  3. 归并排序
  4. 计数排序
  5. 基数排序
  6. AVL 排序
  7. 堆排序

最短路径算法——

  1. 广度优先搜索
  2. DAG 松弛
  3. 深度优先搜索
  4. 拓扑排序
  5. Bellman Ford
  6. Dijkstra
  7. Johnson
  8. Floyd-Warshall

2. 设计您自己的递归算法

  1. 蛮力法
  2. 减小与征服
  3. 分而治之
  4. 动态规划
  5. 贪心/增量

GitHub

查看 Github