用O(n)复杂度学习大O符号

简体中文 English

大O符号是我在大学里学过的东西之一，但是我从来没有真正掌握过这个概念。我知道的足够多，可以回答一些非常基本的问题，但仅此而已。从那以后，一切都没有改变，因为自从我开始工作以来，我没有使用过或听到过我的任何同事提到它。所以，我想我应该花些时间回顾一下，写这篇文章，总结一下大0符号的基础知识，并附上一些代码示例来帮助解释它。

那么，什么是大0符号？简单来说:

  • 它是算法复杂性的相对表现。
  • 它描述了算法如何执行和缩放。
  • 它描述了一个函数增长率的上限，可以认为是最坏的情况。

现在快速看一下语法:O(n2）。

n是函数作为输入接收的元素数。这个例子是说n输入，其复杂度等于n2。

常见复杂性的比较

从这张表中可以看出，随着函数复杂度的增加，完成一个函数所需的计算次数或时间会显著增加。因此，我们希望将这种增长保持在尽可能低的水平，因为如果随着输入的增加，函数不能很好地扩展，可能会出现性能问题。

bigo

显示操作数量如何随着复杂性增加的图表。

一些代码示例应该有助于澄清复杂性是如何影响性能的。下面的代码是用Java编写的，但是很明显，它也可以用其他语言编写。

O(1)

public boolean isFirstNumberEqualToOne(List<Integer> numbers) {
  return numbers.get(0) == 1;
}

O(1)表示一个函数，无论输入大小如何，该函数总是采用相同的取值。

O(n)

public boolean containsNumber(List<Integer> numbers, int comparisonNumber) {
  for(Integer number : numbers) {
    if(number == comparisonNumber) {
      return true;
    }
  }
  return false;
}

O(n)表示与输入数量成正比线性增长的函数的复杂性。这是一个很好的例子，说明了大0符号是如何描述最坏的情况因为函数可以返回真在读取第一个元素或错误的读完所有内容后n元素。

O(n2）

public static boolean containsDuplicates(List<String> input) {
  for (int outer = 0; outer < input.size(); outer++) {
    for (int inner = 0; inner < input.size(); inner++) {
      if (outer != inner && input.get(outer).equals(input.get(inner))) {
        return true;
      }
    }
  }
  return false;
}

O(n2）表示其复杂度与输入大小的平方成正比的函数。通过输入添加更多的嵌套迭代将会增加复杂性O(n3）总共3次迭代O(n4）总共4次迭代。

O(2n）

public int fibonacci(int number) {
  if (number <= 1) {
    return number;
  } else {
    return fibonacci(number - 1) + fibonacci(number - 2);
  }
}

O(2n）表示一个函数，该函数对输入中的每个元素的性能都加倍。这个例子是斐波那契数的递归计算。该功能属于O(2n）因为对于每个输入数字，函数递归地调用它自己两次，直到该数字小于或等于1。

o(对数n)

public boolean containsNumber(List<Integer> numbers, int comparisonNumber) {
  int low = 0;
  int high = numbers.size() - 1;
  while (low <= high) {
    int middle = low + (high - low) / 2;
    if (comparisonNumber < numbers.get(middle)) {
      high = middle - 1;
    } else if (comparisonNumber > numbers.get(middle)) {
      low = middle + 1;
    } else {
      return true;
    }
  }
  return false;
}

o(对数n)表示一个函数，它的复杂度随着输入大小的增加而对数增加。这使得o(对数n)函数的伸缩性非常好，因此处理较大的输入不太可能导致性能问题。上面的示例使用二分搜索法来检查输入列表是否包含某个数字。简而言之，它会在每次迭代时将列表一分为二，直到找到编号或读取最后一个元素。此方法的功能与O(n)示例——尽管实现完全不同，而且更难理解。但是，如果输入更大，这将获得更好的性能(如表中所示)。

这种实现的缺点是，二分搜索法依赖于已经处于正确顺序的元素。如果在遍历元素之前需要对元素进行排序，这就增加了一点性能开销。

关于大0符号还有很多内容要讲，但希望你现在已经对大0符号的含义有了基本的了解，并且知道如何将它翻译成你编写的代码。