大O表示法

大O用来表示上界的，当用它作为算法的最坏情况运行时间的上界，就是对任意数据输入的运行时间的上界。
不同的输入和数据规模都会影响程序的运行时间！时间复杂度主要考虑的是数据规模的影响！

O(1) 描述了一种无论输入数据集的大小如何总是在相同的时间（或空间）内运行的算法。

  1. bool IsFirstElementNull(IList<String> elements)
  2. {
  3.     return elements[0] == null;
  4. }

O(N) 描述了一种性能线性增长并且与输入数据集的大小成正比的算法。

  1. bool ContainsValue(IEnumerable<string> elements, string value)
  2. {
  3.     foreach (var element in elements)
  4.     {
  5.         if (element == value) return true; 
  6.     } 
  7.     return false; 
  8. }

O(N²) 表示一种性能与输入数据集大小的平方成正比的算法，常见于涉及数据集嵌套迭代的算法中。更深的嵌套迭代将导致 O(N³)、O(N⁴) 等。

O(2^N) 表示一种随着对输入数据集的每次加法而增长加倍的算法。O(2^N) 函数的增长曲线是指数 —— 从非常小的开始，然后是急剧上升。O(2^N) 函数的一个例子是 Fibonacci 数的递归计算。

  1. int Fibonacci(int number)
  2. {
  3.     if (number <= 1) return number;
  4.     return Fibonacci(number - 2) + Fibonacci(number - 1); 
  5. }

O(logn)表示运行时间与数据量规模的变化率成对数。能达到这种事很优秀了，因为随着规模增大，运行时间增加很少。
image.png
image.png

  1. int sum = 1;
  2. while(sum < n) {
  3.     sum = sum * 2;
  4. }