PDF《数据结构与算法（DSA）》

当你玩游戏,你会设计一个策略(策略就是 算法)来帮自己赢得比赛.同样的,对计算机来说,算法就是解决问题的时候 一系列的指令 『算法是执行任务的指令』 算法也分为 好 的算法和 坏 的算法,运行时间短的是好的算法,运行时 间长的就是坏的算法.坏的算法会花费更多的时间和金钱 我们将介绍一些算法的基本概念,此外,还将学习如何区分 快 的算法和 慢 的算法,更有趣的是,我们将能够 测量 算法的性能并加以改善 4. 如何提高你的编程技能? 改进事物的第一步是测量它 『如果你不能测量某物,你就无法理解它.如果你不能理解它,你就无法控制它.如果你 无法控制它,你就无法改善它』 ――H. J. Harrington 那么,如何 测量 你的代码呢?用运行了多长时间来测量吗?看似不错,但 是你要知道相同的代码,在移动设备和在 PC 上运行花费的时间是不一样的. 为了回答以上问题,我们得先引进一些概念来阐述它,比如:时间复杂度 (time complexity) 时间复杂度 时间复杂度(或运行时间),它是预估运行算法所花费的 时间 . 注意, 它不是指算法运行耗费的真正时间.而是指算法执行了基本操作的数量级 时间复杂度与算法的时间长短无关.而是执行了多少操作.程序执行的指令的数量受 输入的大小和元素的排列方式的影响 比如,你想要对一组数字进行排序.如果元素已经按照顺序排好序,程序 将执行更少的操作步数.如果数组是反序的,则需要更多的交换操作来进行排 序 对于每一个算法,我们都有以下时间复杂度: ? 最坏情况时间复杂度 ? 最好情况时间复杂度 ? 平均情况时间复杂度 我们通常更关心最坏情况时间复杂度,虽然我们期望碰到到最好的情况,但 要做最坏的打算 以下是这一个关于如何计算时间复杂度的代码示例:在数组中找到最小的数 字1. function getMin(n) { 2. const array = Array.from(n);

3. let min;

4. array.forEach(element =>

{ 5. if(min === undefined || element <

min) { 6. min = element;

7. } 8. });

9. return min;

10.} 11.// 平均情况: 随机顺序 12.console.log(getMin([9,20,4,21,49,39]));

13.// 最好情况: 顺序数组 14.console.log(getMin([4, 9, 20, 21, 39, 49]));

15.// 最坏情况: 反序数组 16.console.log(getMin([49, 39, 21, 20, 9, 4]));

我们假设输入数组 n 作为函数 getMin()的参数,为了简单起见,我们假设 每一行代码在 CPU 中执行占用的时间都是相同的 我们来计算一下所有操作步数之和: ? 第2行:1 步操作 ? 第3行:1 步操作 ? 第4-8 行:它是一个执行 n 次的循环操作 ? 第5行:1 步操作(循环内) ? 第6行:这一步是条件成立才会执行.但是参考上文,我们直接考虑最 坏的情况,假设它每次都会执行,因此也算

1 步操作(循环内) ? 第9行:1 步操作 所以,我们在循环外有

3 步操作,在array.forEach 块中有

2 步操作.因为循 环的大小是 n,所以一共有 2(n)+3 步操作 但是,这个表达式有点太过具体,很难将算法与它进行比较.我们将使用 渐近分析 来进一步简化这个表达式 渐进分析 渐近分析就是把函数的值近似为无穷大.在上个例子 2(n) +

3 中,我们可 以将它概括为 k(n) + c. 随着 n 值的增加,常数 c 的大小对函数结果的影响力越 来越小,如下表所示: n (size) operations result

1 2(1) +

3 5

10 2(10) +

3 23

100 2(100) +

3 203 1,000 2(1,000) +