一键三连是关阿姨更新笔记的动力～

1、算法的评估

算法（Algorithm）是指用来操作数据、解决程序问题的一系列方法。

对于同一个问题，使用不同的算法，也许最终得到的结果是一样的，但在过程中消耗的资源和时间却会有很大的区别。就比如拧一个螺母，扳手和钳子都可以胜任，但使用钳子拧螺母肯定没有扳手的效率高。

2、斐波那契数引入复杂度分析

计时工具（不用敲）

那么我们应该如何去衡量不同算法之间的优劣呢？

3.事后统计法

通过统计、监控，利用计算机计时器对不同算法的运行时间进行比较，从而确定算法效率的高低，但有非常大的局限性：

• 测试结果非常依赖测试环境

• 测试结果受数据规模的影响很大

4.事前分析估算

在计算机程序编制前，依据统计方法对算法进行估算。

大家想一下，当我们要实现一个功能的时候，更多的希望快速知道几种解法中的最优解然后去实现，而不是花大力气去把每种解法都做出来再测试得到结果，因为太低效。

所以我们需要在代码执行前对影响代码效率的因素（如时间、空间复杂度等）做一个评估。因此我们需要通过复杂度分析来决策，下面我们主要讲解面试中最高频的时间复杂度。

时间维度：是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。

空间维度：是指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述。

5.推导大O阶方法

算法的执行效率，粗略地讲，就是算法代码执行的时间。但是，如何在不运行代码的情况下，用“肉眼”得到一段代码的执行时间呢？这里有段非常简单的代码，现在，我就带你一块来估算一下这段代码的执行时间。

尽管我们不知道unit_time的具体值，但是通过这几段代码执行时间的推导过程，我们可以得到一个非常重要的规律，那就是，所有代码的执行时间T(n)与每行代码的执行次数n成正比。

我们可以把这个规律总结成一个公式。注意，大O就要登场了！

• T(n)表示代码执行的时间；

• n表示数据规模的大小；

• f(n)表示每行代码执行的次数总和。

• 因为这是一个公式，所以用f(n)来表示。公式中的O，表示代码的执行时间T(n)与f(n)表达式成正比。

1. 公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。用大O表示法表示刚讲的那两段代码的时间复杂度，就可以记为：T(n) = O(n)； T(n) = O(n^2)。

2. 大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。一般随着n的增大，T(n)增长最慢的算法为最优算法。

6.总结

• 用常数1取代运行时间中的所有加法常数

• 在修改后的运行次数函数中，只保留最高阶项

• 如果最高阶项存在且系数不是1，则去除去除与这个项相乘的系数

一键三连是关阿姨更新笔记的动力～