• 常数阶O(1)
• 线性阶O(n)
• 平方阶O(n²)
• 对数阶O(logn)
• 线性对数阶O(nlogn)

O(次数), 代码执行的次数, 即算法复杂度

O(1) 常数阶 (Constant Time 常数时间)

没有循环\递归, 执行一次完事

并不依赖某个变量, 不受变量影响, 执行时间是固定的

这里说的变量如循环中的 "循环次数" 这种影响执行时间的变量

print "hello";

print "hello";
print "hello";
print "hello";

void swapTwoInts(int &a, int &b){
  int temp = a;
  a = b;
  b = temp;
}

O(n)

for(int i = 0; i < n; i++)// 一点点增加, 线性的变化
  print "hello";

for(int i = 0; i < n; i = i + 2)
  print "hello";

O(n²) 平方阶

比如冒泡排序算法

嵌套循环, 外层每循环一次都要执行一遍内层的 O(n), 就描述成 O(n²)

内层算法的执行次数取决于外层变量的值

for(int i = 0; i < n; i++)//两层线性的变化
  for(int j = 0; j < n; j++)
    print "hello";