算法是一个通用的，解决某种问题的指令列表。它是用于解决一类问题任何实例的方法，给定特定输入会产生期望的结果。另一方面，程序是使用某种编程语言编码的算法。由于程序员知识水平各异且所使用的编程语言各有不同，存在描述相同算法的不同程序。一个普遍的现象是，刚接触计算机的学生会将自己的程序和其他人的相比较。你可能注意到，这些程序看起来很相似。那么当两个看起来不同的程序解决同样的问题时，哪一个更好呢? 要探讨这种差异，请参考如下的函数sum_of_n，该函数计算前n 个整数的和。
// sum_of_n.ts
function sum_of_n(n: number): number {
let sum: number = 0;
for (let i = 0; i < n; i++) {
sum += i;
}
return sum;
}
该算法使用初始值为 0 的累加器变量。然后迭代 n 个整数，将每个值依次加到累加器。
现在再看看下面的函数，可以看到这个函数本质上和前一个函数在做同样的事情。不直观的原因在于编码习惯不好，代码中没有使用良好的标识符名称，所以代码不易读，且在迭代步骤中使用了一个额外的赋值语句，这个语句其实是不必要的。
// foo.ts
function foo(tom: number): number {
let fred = 0;
for (let bill = 0; bill < tom; bill ++) {
let barney = bill;
fred = fred + barney;
}
return fred;
}
之前提的问题：哪个函数更好？答案其实取决于你的评价标准。如果你关注可读性，函数 sum_of_n 肯定比 foo 好。你可能已经在各种介绍编程的书或课程中看到过类似例子，其目的之一就是帮助你编写易于阅读和理解的程序。然而，这里，我们对算法本身的陈述更感兴趣（干净的写法当然重要，但那不属于算法和数据结构的知识）。
算法分析是基于算法使用的资源量来进行比较的。说一个算法比另一个算法好就在于它在使用资源方面更有效率，或者说使用了更少的资源。从这个角度来看，上面两个函数看起来很相似，它们都使用基本相同的算法来解决求和问题。在资源计算这点上，重要的是要找准真正用于计算的资源。评价算法使用资源往往要从时间和空间两方面来看。
算法使用的空间指的是内存消耗，解决方案所需的内存通常由问题本身的规模和性质决定。但有时，部分算法会有一些特殊的空间需求，这种情况下需要非常仔细地审查。
算法使用的时间就是指算法执行所有步骤经过的时间，这种评价方式也被称为算法的执行时间，可以通过基准分析来测量函数sum_of_n 的执行时间。
在 JS 中，可以记录函数运行前后的时间来计算代码运行时间。通过在开始和结束的时候调用 console.time() 和 console.timeEnd()，就可以得到函数执行时间。
// sum_of_n 性能测试
export const bigOPerformanceTest = () => {
for (let i = 0; i < 5; i++) {
console.time('sumofn');
let sum = sum_of_n (500000);
console.timeEnd('sumofn');
}
};
执行这个函数5 次，每次计算前500,000 个整数的和，得到了如下结果:
sumofn: 2.701171875 ms
sumofn: 1.565185546875 ms
sumofn: 4.656982421875 ms
sumofn: 1.456787109375 ms
sumofn: 5.56982421875 ms
我们发现时间是相当一致的，执行这个函数平均需要 6 毫秒。如果我们运行计算前1,000,000 个整数的和，其结果如下：
sumofn: 3.926025390625 ms
sumofn: 10.912841796875 ms
sumofn: 3.026123046875 ms
sumofn: 1.31494140625 ms
sumofn: 1.23828125 ms
可以看到，差不多是计算前 500,000 个整数耗时的二倍，这说明算法的执行时间和计算规模成正比。现在考虑如下的函数，它也是计算前 n 个整数的和，只是不同于上一个sum_of_n 函数的思路，它利用数学公式 来计算，效率更高。
function sum_of_n2(n: number): number {
return n * (n + 1) / 2;
}
修改 bigOPerformanceTest 中的 sum_of_n 函数，然后再做同样的基准测试，使用 3 个不同的 n （100,000、500,000、1,000,000），每个计算 5 次取均值，得到了如下结果：
sumofn2: 0.001953125 ms
sumofn2: 0.00390625 ms
sumofn2: 0.01098632 ms
在这个输出中有两点要重点关注，首先上面记录的执行时间可以按纳秒计，比之前任何例子都短，这 3 个计算时间都在0.0046 毫秒左右，和上面的6 毫秒可是差着几个数量级。其次是执行时间和 n 无关，n 增大了，但计算时间不变，看起来此时计算几乎不受 n 的影响。
这个基准测试告诉我们，使用迭代的解决方案 sum_of_n 做了更多的工作，因为一些程序步骤被重复执行，这是它需要更长时间的原因。此外，迭代方案执行所需时间随着n 递增。另外要意识到，如果在不同计算机上或者使用不用的编程语言运行类似函数，得到的结果也不同。
我们需要一个更好的方法来描述这些算法的执行时间。基准测试计算的是程序执行的实际时间，但它并不真正地提供给我们一个有用的度量，因为执行时间取决于特定的机器，且毫秒，纳秒间也涉及到数量级转换。我们希望有一个独立于所使用的程序或计算机的度量，这个度量能独立地判断算法，并且可以用于比较不同算法实现的效率，就像加速度这个度量值能明确指出速度每秒的改变值一样。在算法分析领域，大O 分析法就是一种很好度量方法。
