时间复杂度_空间复杂度

复杂度：衡量一个算法的效率的

时间复杂度

算法中的基本操作的执行次数，为算法的时间复杂度。

// 请计算一下func1基本操作执行了多少次？
void func1(int N){
          
   
   int count = 0;
   for (int i = 0; i < N ; i++) {
          
     //执行了N*N次
       for (int j = 0; j < N ; j++) {
          
   
           count++;
       }
   }
   for (int k = 0; k < 2 * N ; k++) {
          
     //执行了2*N次
       count++;
   }
  int M = 10;
  while ((M--) > 0) {
          
    //执行了10次
       count++;
   }
     System.out.println(count);
}

所以Func1执行的基本操作次数：N^2+2N+10 推导大O阶方法： 1、用常数1取代运行时间中的所有加法常数。N^2+2N+1 2、在修改后的运行次数函数中，只保留最高阶项。N^2 3、如最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。N^2 使用大O的渐进表示法以后，Func1的时间复杂度为 O(N^2)

冒泡排序

void bubbleSort(int[] array) {
          
   
   for (int end = array.length; end > 0; end--) {
          
   
       boolean sorted = true;
       for (int i = 1; i < end; i++) {
          
   
           if (array[i - 1] > array[i]) {
          
   
                Swap(array, i - 1, i);
                sorted = false;
           }
       }
       if (sorted == true) {
          
   
           break;
       }
   }
}

最坏情况(时间复杂度)：O(N^2) 最好情况：O(N)

二分查找

int binarySearch(int[] array, int value) {
          
   
   int begin = 0;
   int end = array.length - 1;
   while (begin <= end) {
          
   
       int mid = begin + ((end-begin) / 2);
       if (array[mid] < value)
           begin = mid + 1;
       else if (array[mid] > value)
           end = mid - 1;
       else
           return mid;
   }
   return -1; 
}

时间复杂度：O(log2n)

计算阶乘递归factorial的时间复杂度？

long factorial(int N) {
          
   
 return N < 2 ? N : factorial(N-1) * N; }

时间复杂度：O(N) 计算斐波那契递归fibonacci的时间复杂度？

int fibonacci(int N) {
          
   
 return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}

时间复杂度：O(2^N-1)

空间复杂度

一个算法在运行过程中临时占用存储空间大小的量度 计算bubbleSort的空间复杂度？

// 计算bubbleSort的空间复杂度？
void bubbleSort(int[] array) {
          
   
for (int end = array.length; end > 0; end--) {
          
   
     boolean sorted = true;
     for (int i = 1; i < end; i++) {
          
   
         if (array[i - 1] > array[i]) {
          
   
             Swap(array, i - 1, i);
             sorted = false;
         }
     }
     if (sorted == true) {
          
   
         break;
     }
 }
}

空间复杂度：O(1) 计算fibonacci的空间复杂度？

// 计算fibonacci的空间复杂度？
int[] fibonacci(int n) {
          
   
long[] fibArray = new long[n + 1];
fibArray[0] = 0;
fibArray[1] = 1;
for (int i = 2; i <= n ; i++) {
          
   
  fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
 }
return fibArray; }

空间复杂度：O(n) // 计算阶乘递归Factorial的时间复杂度？

long factorial(int N) {
          
   
 return N < 2 ? N : factorial(N-1)*N; }

空间复杂度：O(n)