【数据结构 & 空间复杂度】

本文标签:  时间复杂度和空间复杂度

前言

我们知道 递归代码 需要重复计算大量的数据,所以并不是说代码越简洁,效率就越高,那么我们如何去判断一个算法的优劣呢,因此我们就引出了时间复杂度这一概念.

 一、什么是时间复杂度？编辑

是不是很疑惑,别急,我们慢慢来.

先上概念:

复杂度：又称渐进复杂度。它又可以分为时间复杂度和空间复杂度;

时间复杂度通常是用来衡量算法的优劣的，衡量算法的时间严格来讲是很难衡量的，由于不同的机器性能不用环境都会造成不同的执行时间。算法的执行时间和语句的执行次数成正比，因此通过机器执行测试来推断执行时间。其实就是算法（代码）的执行效率，算法(代码)的执行时间。 

二、时间复杂度的分析与计算. 

        首先我们要知道的是时间复杂度的计算并不是去计算这段代码它真正意义上到底跑了多少秒,例如两台不同的机器,我们需要它们去计算10000个数,A机器配置效率很高,可能很快就跑完了,但是如果用配置很低的B机器去计算,效率就会很慢(ps:就好比某些学校的机房).                       所以我们算的并不是代码的运行时间,而是计算代码的执行次数.

1.计算时间复杂度(代码的执行次数)

我们先来看一个简单的代码

void Func1(int N)
{
     int count = 0;
     //这是第一个部分,有两层for循环,N*N次
     for (int i = 0; i < N ; ++ i)
 {
         for (int j = 0; j < N ; ++ j)
         {
             ++count;
         }
 }
//这是第二个部分,2*N次
 for (int k = 0; k < 2 * N ; ++ k)
 {
    ++count;
 }
//这是第三个循环,10次--
 int M = 10;
 while (M--)
 {
     ++count;
 }
 printf("%d\n", count);
}

2.分析时间复杂度 

我们先来计算Func1函数执行了多少次代码,可以看到第一个部分里有两层循环,外层循环执行一次,内存循环就要执行N次,所以我们可以得到执行次数是 N*N 次;再看第二部分, 因为 for 循环里判断条件是<2*N ,所以循环执行 2*N 次;其次第三部分 M-- 要进行 10 次.所以准确的次数就是  N^2+2*N+10 次,那我们这段代码的时间复杂度是这个吗,其实并不是.

假设 N 分别是 10 , 100, 1000,我们得到以下算式:

 我们仔细观察,不难发现,随着 N 的增大,表达式 N*N+2*N+10 表达式中 N^2 这一项的结果对整个表达式的影响是最大,从这一角度去看,我们要知道时间复杂度本质上其实是一个估算,是去看表达式中影响最大的那一项,其他项对结果的影响是微乎其微的.

当N变得越来越大时，公式中的低阶，常量，系数三部分影响不了其增长趋势，所以可以直接忽略他们,

只记录一个最大的量级就可以了.

(也就是说用的并不是准确值（事实上也无法得出），而是根据合理方法得到的预估值).

---

三、1. 时间复杂度的表示 

实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次

数，那么这里我们使用大O的渐进表示法。

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

大O时间复杂度也叫作渐进时间复杂度，简称时间复杂度.(其实就是一个估算,记住O(频度)就可以了).通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数. 所以上述代码的时间复杂度就可以表示为:O(N^2).

O(频度):这里的频度为最简之后所得的频度。或许各位对最简化频度并不是很清楚。这里给大家总结一下，在数据结构中，频度表达式可以这样简化：

• 用常数1取代运行时间中的所有加法常数。
• 在修改后的运行次数函数中，只保留最高阶项的那一项。
• 如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O(频度).

1.代码演示:

// 计算Func2的时间复杂度？
void Func2(int N)
{
 int count = 0;
 for (int k = 0; k < 2 * N ; ++ k)
 {
 ++count;
 }
 int M = 10;
 while (M--)
 {
 ++count;
 }
 printf("%d\n", count);
}

  算法执行了2N+10次，通过推导大O阶方法知道，常数化为1保留最高阶项,所以时间复杂度为 O(N),

2.代码演示:

//计算Func3的时间复杂度？
void Func3(int N, int M)
{
     int count = 0;
     for (int k = 0; k < M; ++ k)
     {
         ++count;
     }
     for (int k = 0; k < N ; ++ k)
     {
         ++count;
     }

     printf("%d\n", count);
}

Func3的时间复杂度是O(M+N),因为我们并不知道M要执行多少次,也不知道N要执行多少次,他们俩都是一个未知数,也就是说,算法的时间复杂度有可能是一个未知数也有可能是多个未知数.

但是如果我们给这一题加上条件: 1.M远大于N,这里的时间复杂度就是O(M),又或者给出的条件是2.M和N差不多大,则时间复杂度就是O(M)或者O(N).所以我们要根据实际情况得出算法的时间复杂度.(并不是说一层循环就是O(N),两层循环就是O(N^2),我们要根据算法的实际情况判断)

3.OK,再来:

//计算Func4的时间复杂度？
void Func4(int N)
{
 int count = 0;
 for (int k = 0; k < 100; ++ k)
 {
      ++count;
 }
 printf("%d\n", count);
}

这里给了一个N,但是程序中并没有使用到N;又因为上述文中,大O简化频度规定过用常数1取代运行时间中的所有加法常数。只要我们这里是确定的常数次,不管他是多少都用 1 替代 , 所以这里的时间复杂度是O(1).同理,假设题目说一个算法的时间复杂度是O(1),我们就能知道算法的执行次数是它的常数次,  这一题的常数无论怎么变,对N的影响很小,算法的时间复杂度取决于 N  .

//计算strchr的时间复杂度？
const char * strchr ( const char * str, char character )
{
  while(*str != '\0')
 {
      if(*str == character)
          return str;
      
      ++str;
 }
  
  return NULL;
}

  这段代码的意思是在一个字符串中找到一个指定的字符,如果找到返回,没有找到,str继续++,如果走到最后都没有找到,那就返回NULL.这题我们要分情况讨论:

举个例子,假设有字符串"dhfgsfsdsds".

1.假设找字符's':我们在字符的二分之一处找到了.(平均,O(N/2))

2.假设找字符'd',开头就找到了(最好的情况,O(1))

3.假设找字符'x',找不到(最坏的情况,O(N))

所以,一个算法的时间复杂度存在最好,平均和最坏的情况,由上可知,虽坏的情况我们的时间复杂度就是O(N),平均的情况要找O(N/2),最好的情况要找O(1).

数据结构中规定:当算法存在这三种情况的时候,看最坏的情况,也就是说时间复杂度取最坏的情况.

5.代码演示:

//计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
 assert(a);
 for (size_t end = n; end > 0; --end)
 {
     int exchange = 0;
         for (size_t i = 1; i < end; ++i)
         {
             if (a[i-1] > a[i])
             {
                 Swap(&a[i-1], &a[i]);
                 exchange = 1;
             }
 }
     if (exchange == 0)
     break;
 }

假设我们冒泡排序 4 个数，第一趟比较次数 4 次，第二趟 3 次，第三趟 2 次....(第一趟的数还要和数列末项的后面一块空间比较一次,这里是比较次数 4 次,如果是交换次数则为 3 次), 如果我们要冒泡排序 N 个数，第一趟比较 N 次,第二趟 N-1 次,第三趟 N-2 次...第N趟则为 1 次(最后一趟只剩一个数了,不用比较所以是 1 ),将每一项相加后我们发现冒泡排序的算法其实就是一个等差数列(N+1)*N/2)   , 拆分后这个表达式的最大项是  N^2  ,所以它的时间复杂度是O(N^2).

6.代码演示

// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{
 assert(a);
 int begin = 0;
 int end = n;
 while (begin < end)
 {
 int mid = begin + ((end-begin)>>1);
 if (a[mid] < x)
 begin = mid+1;
 else if (a[mid] > x)
 end = mid;
 else
 return mid;
 }
 return -1;
}

这是一二分查找的算法,在一个有序数组中查找指定元素,这里不细说它的算法思想,不了解得的可以参考一下我写的CSDN博客.如果不用二分查找算法来找一个数组中的指定元素,它的时间复杂度显而易见就是O(N),但是二分查找算法是要分情况讨论的.

假设有一数组 :{ 0,1,2,3,4,5,6,7,8,9 }

1.最好的情况:  要找的元素是 4 数组下标的平均值mid就是 4 ,所以时间复杂度是O(1);

2.最坏的情况:  要找的元素是 10 ,找不到,时间复杂度是O(N);

我们重点要看的是第三种情况:假设要找的元素是 8 ,第一次折半查找到的元素是 4 ,小于我们的 8 ,那么 begin=mid+1,此时是找 5 和 9的中间值,得到 7 ,仍然小于 8 ,begin=mid+1,再找 8 和 9 的中间值得到指定元素 8 . 可能这里我们还是不能理解它的时间复杂度,现在我们可以将刚刚的过程反过来看,每次都是折一半得到一个值, 假设我们找了 X 次找到指定元素,如果再进行 X 次  乘2后就会得到原来的所有元素.(可以想象一下纸张对折X次后又将它 X 次乘 2 的方式再展开.)

我们可以得到 1*2*2*2...*2 = N,可以转换为2^X=N, X=,因为算法的复杂度计算,可以省略简写成logN,因为很多地方不好写底数,所以折半查找算法的时间复杂度就是O(logN).

 7.代码如下:

// 计算阶乘递归Factorial的时间复杂度？
long long Factorial(size_t N)
{
 return N < 2 ? N : Factorial(N-1)*N;
}

递归的表达式为 1*2*3*4*5*6*7...*n,  如果递归了 N 次,每次递归运算就是O(1),整体的复杂度就是O(N), 递归是函数调用多次,也就是调用了N次,每次都是O(1).

8.代码如下:

// 求递归斐波那契数复杂度
long Fibonacci(int n) {
 5     if (n == 0)
 6         return 0;
 7     else if (n == 1)
 8         return 1;
 9     else
10         return Fibonacci(n - 1) + Fibonacci(n-2);
11 }

斐波那契数指的是这样一个数列：0、1、1、2、3、5、8、13...前两项之和等于第三项,第一项是0,第二项和第三项都是1,所以递归就可以这样规定F（0）=0，F（1）=1，F（n=F(n-1)+F(n-2),所以求F(n)必须先计算F(n-1)和F(n-2),而要计算F(n-1)和F(n-2)，又必须先计算F(n-3)和F(n-4)...以此类推要进行重复大量的计算,算法的复杂度呈指数上升,所以它的时间复杂度是O(N^2).

四、 常见的时间复杂度对比

经过上面的练习,我们知道了各种各样的时间复杂度:O(N^2),O(N),O(logN),O(1)...,在他们之间也有着对比.

如图:

由此可见,O(logN) 是最好的时间复杂度.

---

 一、空间复杂度概念？

老规矩先上定义:

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用

了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计

算规则基本跟实践复杂度类似，也使用大O渐进表示法。

前面关于时间复杂度我们知道 计算空间复杂度并不是计算算法的执行时间,算的是算法的执行次数,而空间复杂度同理,不算空间,算的是变量的个数.它同样和时间复杂度一样是一个估算,与时间复杂度的规定大同小异.

二、实例展示

1.冒泡排序：

// 计算BubbleSort的空间复杂度？
void BubbleSort(int* a, int n)
{
 assert(a);
 for (size_t end = n; end > 0; --end)
 {
 int exchange = 0;
 for (size_t i = 1; i < end; ++i)
 {
 if (a[i-1] > a[i])
 {
 Swap(&a[i-1], &a[i]);
 exchange = 1;
 }
 }
 if (exchange == 0)
 break;
 }
}

 解析:空间复杂度也是用大O渐进法,类似于时间复杂度的方式,是去计算变量的个数,  如上冒泡排序的空间复杂度是O(1) ,变量有 a,n,szie_t end,size_t i,exchange.总共是常数5个,常数都看作是 1,所以空间复杂度是O(1).

这里我们要注意,时间是可以累计的,而空间是不累计的,也就是说时间用完了还存在,而空间被开辟后用完可以丢弃销毁,比如:一个循环走了N次,它重复利用的是一个空间.用不到了就可以被销毁;递归同样也是一个道理,在递归时开辟了一块又一块的空间,当计算往下走时,保留空间,返回时,用不到的空间就会被销毁.

2.斐波那契数:

// 计算Fibonacci的空间复杂度？
long long* Fibonacci(size_t n)
{
     if(n==0)
          return NULL;
     long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));

     fibArray[0] = 0;
     fibArray[1] = 1;
     for (int i = 2; i <= n ; ++i)
     {
           fibArray[i ] = fibArray[ i - 1] + fibArray [i - 2];
     }
     return fibArray ;
}

 解析:(malloc的意思是开辟了 n+1 个 long long 类型变量的数组).

计算变量个数有 n, fibArray, fibArray[0], fibArray[1], i 一共 5 个,但是我们还看见 malloc 函数中有 (n+1) ,所以空间复杂度是 O(N+6) ,随着N的增大, +6 的影响对其影响不大,所以可以忽略不计,最后斐波那契数的空间复杂度是 O(N) .

(大多数情况下,算法的空间复杂度都是O(1),都是常数个变量,此代码中 malloc 是开辟了一个数组.)

3.阶乘递归: 

// 计算阶乘递归Factorial的空间复杂度？
long long Factorial(size_t N)
{
 return N < 2 ? N : Factorial(N-1)*N;
}

解析: 这个代码我们知道,递归调用了 N 次,每一次都调用建立一个栈帧,每个栈帧使用了常数个空间,也就是一次递归的空间复杂度是 O(1) ,而调用了 N 次递归,空间复杂度就是 O(N) .

(虽然递归调用返回时空间销毁,但是我们仍要计算它,可以理解为计算时间复杂度的最坏情况,) 

三、.有复杂度要求的算法题练习

1.题目链接： 力扣--消失的数字

思路一:

数组nums包含 0 ~ n 的所有整数,要找出其中缺的那一个数字,我们按将其数组元素进行排序,例如: [2 ,3, 1, 4, 5, 7, 6, 9],将其排序之后就会变成[1,2,3,4,5,6,7,9].然后就很简单了,要找到消失的数就可以将排序后的元素遍历一遍,看后一个数是不是比前一个数大1,如果不是那就直接找到了.

代码如下:

int missingNumber(int* nums, int numsSize){
    for(int i = numsSize - 1; i > 0; i--)
    {
        //冒泡排序
        flag = 1;
        for(int j = 0; j < i; j++)
        {
            if(nums[i] > nums[i + 1])
            {
                int tmp = nums[i];
                nums[i] = nums[i + 1];
                nums[i + 1] = tmp;
                if(flag)
                    flag = 0;
            }
            if(flag)
                break;
        }
    }
    //检查每个元素前后是否相差为1
    for(int z = 0; z < numsSize - 2; z++)
    {
        if(nums[z + 1] - nums[z] != 1)
            return nums[z + 1] - 1;
    }    
    //考虑头尾
    if(nums[0])
    return 0;
    return numsSize;
}

但是题目要求算法的时间复杂度要求是 O(N) ,如果使用最快的排序只能达到O(N*logN),所以排序并不合适.

思路二:

要求 0 ~ n 中缺失的那个,可以将 0 ~ n 的所有元素相加,得到的结果再与原数组里元素的和相减,结果就得到消失的数字.

代码如下:

int missingNumber(int* nums, int numsSize){
    int misNum = 0;
    for(int j = 0; j < numsSize + 1; j++)
    misNum += j;
    for(int i = 0; i < numsSize; i++)
    misNum -= nums[i];
    return misNum;
}

思路三:

异或:将数组中的数依次跟 0 ~ n 的所有数异或,最后剩下的数据就是缺的那个数字(异或:按位异或相同为 0 ,不同为 1 ).

举例如下:

我们知道相同的数异或到一起就没了,是0. 此题如果把 0 ~ n 的数与原数组里的元素进行异或,然后相同的两个数异或没了,那么剩下的就是消失的那个数,(两数组进行异或时不需要有序,因为异或满足交换律,相同的会消失,最后剩下的就是要求的数)

举例验证:

这个例子我们可以看到虽然数据没有有序,但是相同的两个数被相互消去,得到的是不同的那个数.

代码如下:

int missingNumber(int* nums, int numsSize){
    int x = 0;
    //用for循环求出数组中的异或之和
    for(int i = 0; i < numsSize; i++)
       x ^= nums[i];
    for(int j = 0; j < numsSize + 1; j++)//原数组比0~n少1个数,要+1
    //再和(0~n)之间的数异或
       x ^= j;
    return x;
}

 2.题目链接：力扣--旋转数组

 思路一:

如果要进行一次旋转,有数组 [1,2,3,4,5,6,7,8,9] ,可以先将数组中的最后末尾元素 9 存放到一个变量中,然后将最后一个元素之前的数据依次向后挪动,我们可以定义一个变量 end ,将它依次减减,就可以将元素依次挪动,直到最后首元素空出,再将 9 放进去,这样就完成了旋转了一次,

 代码如下:

void rotate(int* nums, int numsSize, int k)
{
    for(int i=0;i<k;++i )
    {
        //旋转一次
        int tmp=0;
        tmp=nums[numsSize-1];
        for(int end=numsSize-2;end>=0;end--)
        {
            nums[end+1]=nums[end];
        }
        nums[0]=tmp;
    }
}

当前代码的时间复杂度是O(N*K),效率太低.

思路二:

以空间换时间:创建一个新的数组，首先将后 k 个数放到新数组的前 k 项里面，然后再将剩下的数放到新数组里面，(也就是将原数组分两段存放到一个新的数组中)

最后第二个循环是将新数组的内容替换掉原数组中的内容

代码如下:

void rotate(int* nums, int numsSize, int k){
    int nums1[numsSize];
    for(int i=0;i<numsSize;i++)
    {
        nums1[(i+k)%numsSize]=nums[i];
    }
    for(int j=0;j<numsSize;j++)
    {
        nums[j]=nums1[j];
    }
}

numsSize取余是为了防止k的大小长度超过numsSize, 这样的解法时间复杂度符合要求，但是需要额外的空间实现

思路三:

有数组 [1,2,3,4,5,6,7]

先将数组的后 k 个逆置: [1,2,3,4,7,6,5]

再将前 n - k 个逆置: [4,3,2,1,7,6,5]

再整体逆置:[5,6,7,1,2,3,4]

代码如下:

void Reverse(int* nums, int left, int right)

{

	while (left < right)

	{
    int tmp = nums[left];
    nums[left] = nums[right];
    nums[right] = tmp;
    ++left;
    --right;
	}
}

void rotate(int* nums, int numsSize, int k)

{
	if (k >= numsSize)

	{
 		 k %= numsSize;
	}
    Reverse(nums, numsSize - k, numsSize - 1);
    Reverse(nums, 0 , numsSize -k - 1);
    Reverse(nums, 0 , numsSize - 1);
}

 都看到这了给个三连呗

如有不足,还望指出.

【转自：响水网站建设 http://www.1234xp.com/xiangshui.html 复制请保留原URL】