时间复杂度与空间复杂度

算法的复杂度 ：

首先，算法的时间复杂度与空间复杂度 统称为算法的复杂度。

时间复杂度：

• 计算函数语句总的执行次数与问题规模N的函数表达式。

• 一个算法的最坏情况的运行时间是在任意输入下的运行时间的上限。

• 对于某些算法，最坏的运行情况出现的比较频繁。

• 大体上看，平均情况与最坏情况的运行时间基本一样差。

O渐近表示法：算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作T(n)=O(f(n)),它表示随问题规模n的增大，算法的执行时间的增长率和f(n)的增长率相同，称O(f(n))为算法的渐近时间复杂度，即时间复杂度的O渐近表示法。

时间复杂度简单来说就是语句执行的次数。O渐进表示法是控制变化因素，估算n趋于无穷大的情况，是一个估算值。 
O(n)的一般计算方法： 
1. 数执行语句的次数，遇到循环用乘法，顺序执行用加法； 
2. 用O括起来，即O(); 
3. 用常数1取代运行时间中的所有加法常数； 
4. 扔掉低阶，保留最高阶； 

5. 将留下的最高阶的系数换为1。

int x = 1;//时间复杂度为O(1)  

• 1

for(int i=0; i<n; i++) {  
    System.out.println(i);  
}//时间复杂度为O(N)  

• 1
• 2
• 3

int n = 8, count = 0;;  
for(int i=1; i<=n; i *= 2) {  
    count++;  
}  //时间复杂度为O(logN)

• 1
• 2
• 3
• 4

int n = 8, count = 0;;  
for(int i=1; i<=n; i++) {  
    for(int j=1; j<=n; j++) {  
        count++;  
    }  
}  //时间复杂度为O(N^2)

• 1
• 2
• 3
• 4
• 5
• 6

空间复杂度：

• 函数中创建对象的个数关于问题规模的函数表达式
• 不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数，与问题规模没有关系（简单理解就是算法执行时创建的变量个数（包括临时变量）
• 空间可以重用，算递归最坏（最深）的一种情况

二分法查找时间复杂度以及空间复杂度的算法：

先看二分法查找的程序：

int binary_search(int arr[], int key, int sz)  
{  
       int left = 0;  
       int right = sz - 1;  
       int mid = 0;  
       while (left <= right)  
       {  
        mid = left + (right - left) / 2;  
              if (arr[mid] == key)  
              {  
                     return mid;  
              }  
              else if (arr[mid] < key)  
              {  
                     left = mid + 1;  
              }  
              else  
              {  
                     right = mid - 1;  
              }  
       }  
       if (left <= right)  
              return mid;O  
       else  
              return 0;  
}  

二分法查找其实就是将我们要找的数与数组中n个元素中中间的那个元素对比，如果要找的数比中间这个数大（反之我们就在这个数的左边找），我们就在中间的这个数元素右边的数中继续找中间的数与要找的数比较，然后一直循环着个过程一直到找到这个数为止。找到这个数循环过程的总次数就是我们所求的时间复杂度。即：Time=Log₂n。则时间复杂度就为O(Log₂n),在二分查找里因为没有新空间的开辟，只需要开辟固定大小的空间就可以创建这几个变量，所以它的空间复杂度为O(1)。

斐波那契数列

//递归法
int fib(int n)
{
    if(n<3)
        return 1;
    else
    return fib(n-1)+fib(n-2);
}

循环的基本操作次数是n-1，辅助空间是n+1， 
所以，时间复杂度是：O（N^2） 
空间复杂度是：O（N）