关于复杂度的习题（消失的数字）

1.0计算斐波那契数列递归fib的空间复杂度

 //计算斐波那契数列递归fib的空间复杂度
long long Fib(size_t N)
{
  if(N

注：空间是可以重复服务器托管网利用的，不累计的；但是时间是一去不复返，累计的。

递归调用分析：

正是因为空间复杂度可以重复利用，所以斐波那契数列的空间复杂度是O(N)

2.0这道题是leetCode上的面试题

注：这道题的解决方法有很多，关于复杂度我们目的不是怎样解决出这个问题，而是要分析出每种方法的复杂度，选择复杂度优的方法即可，这就是复杂度在实际中的意义。

思路一：排序（用qsort函数快排）–>判断相邻之间相差是不是1

思路一时间复杂度：O(n*log₂N)

思路二：（0+1+2+3+….+n）-（a[0]+a[1]+a[2]+…+a[n-1]）

思路二时间复杂度：O(n)

思路三：异或：

给一个值x=0

x先跟[1,n]的所有值异或， 再跟数组中的每个值异或，最后x就是那个缺的数字

思路三时间复杂度：O(n)

综上：法二和法三符合题意，所以这里我将法三的代码写一下

int missingNumber(int* nums, int numsSize)
{
    int x = 0;
    int i = 0;
    for(i=0;i

其他方法感兴趣可以自己尝试尝试写一下。

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://服务器托管网www.fwqtg.net