算法学习-golang版

N³/6-N²/2+N/3 ~ N³/6。使用 ~f(N) 来表示所有随着 N 的增大除以 f(N) 的结果趋近于 1 的函数。

N³/6-N²/2+N/3 的增长数量级为 O(N³)。增长数量级将算法与它的实现隔离开来，一个算法的增长数量级为 O(N³) 与它是否用 Java 实现，是否运行于特定计算机上无关。

执行最频繁的指令决定了程序执行的总时间，把这些指令称为程序的内循环。

使用成本模型来评估算法，例如数组的访问次数就是一种成本模型。

如果 T(N) ~ aN^blogN，那么 T(2N)/T(N) ~ 2^b。

例如对于暴力的 ThreeSum 算法，近似时间为 ~N³/6。进行如下实验：多次运行该算法，每次取的 N 值为前一次的两倍，统计每次执行的时间，并统计本次运行时间与前一次运行时间的比值，得到如下结果：

可以看到，T(2N)/T(N) ~ 2³，因此可以确定 T(N) ~ aN³logN。

在求近似时，如果低级项的常数系数很大，那么近似的结果就是错误的。

计算机系统会使用缓存技术来组织内存，访问数组相邻的元素会比访问不相邻的元素快很多。

在核反应堆、心脏起搏器或者刹车控制器中的软件，最坏情况下的性能是十分重要的。

通过打乱输入，去除算法对输入的依赖。

将所有操作的总成本除于操作总数来将成本均摊。例如对一个空栈进行 N 次连续的 push() 调用需要访问数组的元素为 N+4+8+16+...+2N=5N-4（N 是向数组写入元素，其余的都是调整数组大小时进行复制需要的访问数组操作），均摊后每次操作访问数组的平均次数为常数。