时间复杂度和空间度

基本概念：
数据：计算机中可以操作的对象；
数据元素：组成数据的，有一定意义的基本单位；
数据项：一个数据元素可由若干个数据项组成。

对于顺序结构来说，删除和插入不方便；而对于物理结构来说，查找不方便。
时间复杂度：
一般情况下，使用O渐进表示法来计算算法的时间复杂度。
一般算法O(n)计算方法：
（1）先找总运行次数（循环对应乘法；顺序对应加法）；
（2）给次数加上O( );
（3）用常数1取代运行时间中的所有加法常数；
（4）在修改后的运行次数函数中，只保留最高阶项；
（5）如果最高阶项系数存在且不是1，则去除与这个项相乘的常数。
递归算法的时间复杂度：递归总次数*每次递归次数。
折半查找的时间复杂度为：O(lgN)。
空间复杂度：函数中创建对象的个数关于问题规模函数表达式，一般情况下用O渐进表示法表示。
以求第5个斐波那契数为例画图分析，求时间复杂度和空间复杂度：

要求第五个斐波那契数，必须知道第四个和第三个斐波那契数；
而要求第四个斐波那契数，必须知道第三个和第二个斐波那契数；
进而要求第三个斐波那契数，必须知道第二个和第一个斐波那契数。
采用尾递归实现斐波那契算法

long fib(long first,long second,long n)
{
   if(n < 3)
 return 1;
   if(n == 3)
 return first+second;
 return fib(second, first+second,n-1);
}
int main()
{
   long ret = 0;
   ret = fib(1,1,N);
   printf("%d\n",ret);
 return 0;
}

分析：假设求第6个斐波那契数，传的实参依次为：
（1，1，6）；
（1，2，5）；
（2，3，4）；
（3，5，3）当n==3时，结束递归。
采用循环实现斐波那契算法

long fib(long first,long second,long n)
{
   int f = first;
   int s = second;
   int tmp = 0;
   if(n < 3)
       return 1;
   if(n == 3)
   {
       return first+second;
   }
   while(1)
   {
       int i = n;
       int ret = 0;
       tmp = f;
       f = s;
       s = tmp+s;
       if(i == 4)
       {
          ret = f+s;
          break;
       }
       n--;
   }
}
int main()
{
   long ret = 0;
   ret = fib(1,1,N);
   printf("%d\n",ret);
   return 0;
}

分析：假设求第6个斐波那契数：
第一次循环:i=6, ret=0, tmp=1, f=1, s=tmp+s=2;
第二次循环:i=5, ret=0, tmp=1, f=2, s=tmp+s=3;
第三次循环:i=4, ret=8, tmp=2, f=3, s=tmp+s=5;