江苏龙网

  1. 主页 > 生活百科 > >

什么是算法的大O表示法( 二 )

大O表示法


【什么是算法的大O表示法】int Fibonacci(int number) {  if (number <= 1) return number;  return Fibonacci(number - 2) + Fibonacci(number - 1);}O(log2n)指数复杂度二分法查找时间复杂度最好的情况是O(1) ， 最坏的情况根据Master定理T(n)=T(n/2)+O(1) ， 所以是O(log2n) 。它的原理是对于已经排序的数据集 ， 先取中间值进行对比 ， 成功即返回否则根据对比结果确定下一次的中间值对比 ， 依次类推
int binarySearch(int[] arr, int value) {  int start = 0, end = arr.length - 1;  while (start <= end) {    int middle = (start + end) / 2;    if (value == arr[middle]) {      return middle;    }    if (value > arr[middle]) {      start = middle + 1;    }    if (value < arr[middle]) {      end = middle - 1;    }  }  ren -1;}算法空间的复杂度空间的复杂度的计算方法和时间复杂度一样 ， 只是这里假设算法的指令、常数、变量和输入数据用到的寄存器相同 ， 而只计算其用到的辅助空间单元个数 。
实际上时间和空间是一对矛盾的冤家 ， 一般情况下要么拿时间换空间 ， 要么拿空间换时间 ， 鱼和熊掌不可兼得 。
复杂度对比算法的复杂度一般从小到大顺序依次是O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < O(2n)

什么是算法的大O表示法

文章插图




推荐阅读


上一篇：何为十八层喝茶,喝茶当心

下一篇：抗癌效果不错的茶,绿茶的防癌与抗癌的效果作用