一般法则

  • for循环 一个for循环的运行时间至多是for循环内部语句的运行时间乘以迭代次数
  • 嵌套的for循环
    从里向外分析循环，一组嵌套循环内部的一条语句总运行时间为该语句的运行时间乘以该组所有的for循环大小的乘积
    以下程序片段为$$ O(N^2) $$
for (i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        k++;
  • 顺序语句 各个语句中最大的运行时间即为顺序语句的运行时间。
    以下程序片段第一个for循环花费$$ O(N) $$，第二个嵌套for循环花费$$ O(N^2) $$，结果为$$ O(N^2) $$
for (i = 0; i < n; i++)
    a[i] = 0;
for (i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        k++;
  • if/else语句 一个if/else语句的运行时间从不超过判断的运行时间再加上分支语句中运行时间长者的总运行时间