17611538698
webmaster@21cto.com

O(n):用于算法复杂度的大O符号表示法

资讯 0 6171 2018-12-01 11:57:08

21CTO导读:大O符号,英语称为Big O Notation,用于描述算法复杂度的渐进表示,它描述了算法如何通过其增长的上界来执行扩展。


bigo.jpg

 
大O算法是我在大学教过的东西之一,但是我其实从来没有掌握过这些概念,读书时我自己觉得能够足够回答这个符号的基本问题。
 
从那时候起没有什么任何改变。从我参加工作以来,也没有用过,也很少听到其他的同事提起过它。
 
在本文中,我想花一些时间来写一篇文章来总结大写O算法的基础知识 ,包括一些代码实例来辅助说明。
 
Big O Natiation是什么?来简单解释一下:
 
1、它是算法复杂度的相对表示方式
2、它描述了算法如何执行与扩展
3、它描述了函数增长能力的上限,可以理解为最不好的情形
 
快速查看算法:O(n2).
 
其中:n是函数作为输入接收的元素个数。上面的公式表示有n个输入,其复杂度为(n2),这是一种速度较慢的排序算法。
 

001.jpg


表1:共同复杂度的比较

 
从上表中可以看到,随着函数的算法复杂度不断增加,完成函数所需要的时间越明显增加。在编程过程中,我们希望让这种递增尽可能地低,如果某个函数在输入增加时不能很好的扩展,那么极有可能导致性能糟糕的问题。
 

 
002.jpg


程序员还是适合用代码说话,下面的代码用Java编写,将有助于你清晰了解算法复杂度是如何影响性能的。
 
O(1)
 
public boolean isFirstNumberEqualToOne(List<Integer> numbers){
return number.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)表示函数的复杂性,也称线性时间,该函数线性增加并与输入数量成正比。 这是Big O Notation如何描述最糟糕情况的一个很好例子,因为函数可以在读取第一个元素后返回true,或者在读取所有n个元素后返回false。这样的算法包括简单查找。
 
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)表示其复杂度与输入大小的平方成正比的函数。 通过输入添加更多嵌套迭代将增加复杂度,其可以表示为具有3次总迭代的O(n3) 和具有4次总迭代的O(n4) 。
 
O(2n)
 
public int fibonacci(int number) {
    if (number <= 1) {
       return number;
    } else {
      return fibonacci(number - 1) + fibonacci(number - 2);
    }
}
 
O(2[size=25]n) 表示一个函数,其性能对于输入中的每个元素都加倍。 这个例子是Fibonacci数组的递归计算。 该函数属于O(2n) ,因为函数递归式为每个输入数字调用两次,直到该数字小于或等于1。[/size]
 
O(log 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(log n) ,也称对数时间,表示随着输入大小的增加其复杂度以对数方式增加的函数。 这使得O(log n) 函数可以很好地扩展,因此处理较大的输入不太可能导致性能问题。 上面的示例使用二进制搜索来检查输入列表是否包含特定数字。
 
简单来说,它在每次迭代时将列表拆分为两个,直到找到数字或读取最后一个元素。 该方法具有与O(n)[size=19] 示例相同的功能 - 尽管实现完全不同并且更难以理解。 但是,通过更大的输入可以获得更好的性能(如上表中所示)。[/size]
 
小结
 
当前,我们获得的启示如下:
 
1 算法的速度指的并非时间,非操作数的增速
2 谈论算法的速度时,我们说的是随着输入的增加,其运行时间将以什么样的速度增加
3 算法的运行时间用大O表示法表示
4 O(log n)比O(n)快,当需要搜索的元素越多时,前者比后者快得越多。
 
关于Big O Notation还能写出很多内容。希望大家对Big O Notation的含义以及如何将其转换为自己编写的代码有一个基本概念。

作者:老夏


评论