什么是算法的大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表示法

文章插图




推荐阅读