关于算法:Algorithms-普林斯顿知识点熟记-Analysis-of-Algorithms

为什么须要剖析算法？

1. 对性能进行预测
2. 进行算法比拟
3. 为后果提供保障
4. 了解实践根底

运算次数为 NlgN 的算法比 n^2 的算法快 50000 倍

双对数（以 2 为底）坐标作图，横坐标是数据量的对数，纵坐标是运行工夫的对数，失去的斜率 k 的值意味着 数据量每增加一倍，所要花费的工夫大概是之前运行工夫的 2^k 倍。比方斜率为 3,1k 用时为 1s，那么 2k 用时就为 1 *2^3 s = 8 s

幂定律

a 取决于电脑自身的硬件和软件等
b 取决于算法

数学模型

计算如下代码片段数组的拜访次数

int sum = 0;
for (int i = 0; i < n; i++)
    for (int j = i+1; j < n; j++)
        for (int k = 1; k < n; k = k*2)
            if (a[i] + a[j] >= a[k]) sum++;

后面两个循环共执行如下次数

第三个循环中，k 的值顺次是

注：

故第三个循环共执行如下次数：

所以整个数组的拜访次数 = 前两个循环的循环次数 第三个循环的次数再 每次循环拜访数组的次数