关于算法: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 的值顺次是

注:

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

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

【腾讯云】轻量 2核2G4M,首年65元

阿里云限时活动-云数据库 RDS MySQL  1核2G配置 1.88/月 速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

您可能还喜欢...

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据