C++ Program Run Time

时间复杂度

  • costs for growth rate representative of most computer algorithm
    • n loglogn logn n nlogn n2 n3 2n
      16 2 4 24 2*24=25 28 212 216
      256 3 8 28 8*28=211 216 224 2256
      1024 3.3 10 210 10*210=213 220 230 21024
      64K 4 16 216 16*216=220 232 248 264K
      1M 4.3 20 220 20*220=224 240 260 21M
      1G 4.9 30 230 30*230=235 260 290 21G
  • 最差，最好，平均
    • 例如顺序搜索
      • 如果在第一个就搜到，那么就是最佳的case
      • 如果搜到最后一个才搜到，那就是最差的case
      • （最佳+最差）/2为平均
    • 一般都是用平均的
  • 上界
    • 大O表示
      • 对一个非负的函数T(n)，T(n)是O(f(n))的当且仅当存在两个非负的c和k，使得T(n)<=cf(n) 对所有n > k;
        • 其中k为n的最小值
    • 大omega
      • 对一个非负的函数T(n)，T(n)是omega(g(n))当且存在两个非负的c和k，使得T(n)>=cg(n) 对所有n > k;
    • 大theta
      • 当上界和下界被同一个常数影响。
  • 例子
  • sum1 = 0; for(k=1;k<=n;k*=2) for(j=1;j<=n;j++) sum1++; sum2 = 0; for(k=1;k<=n;k*=2) for(j=1;j<=k;j++) sum2++;
    • 第一个循环
      • 第一个for执行了logn + 1次
      • 第二个for执行了n次
        • 那么复杂度为nlogn
    • 第二个循环
      • 第一个for执行了logn + 1次
      • 第二个for执行了执行了k次，k=2i
        • 那么复杂度为n
  • 常用算法的时间复杂度

  • 搜索

    • 算法 数据结构 平均时间复杂度
      二分搜索 数组查n个元素 logn|
      顺序查找 数组查n个元素 n|
      最短路（乱序数组） V个点和E条边 V2
      最短路（bellman-ford） V个点和E条边 V*E

  • 排序

    • 算法 数据结构 平均时间复杂度
      快速排序 数组 nlogn
      归并排序 数组 nlogn
      堆排序 数组 nlogn
      冒泡排序 数组 n2
      插入排序 数组 n2
      选择排序 数组 n2
      桶排序 数组 n+k
      计数排序 数组 n*k

算法加速

  • focus on算法主要消耗时间的部分
  • 先优化算法，再优化代码
c++
Comments

Comments