精华内容
下载资源
问答
  • 空间复杂度计算方法
    2020-05-26 15:52:51

    原文链接:https://ask.csdn.net/questions/326029?sort=id
    算法题中经常有空间复杂度的限制,特此记录

    简单来说,假设原始数据大小为n,一个算法需要m大小的内存才能运行,那么我们就有一个函数f(n)=m。这个函数去掉常数项和尾数项就是空间复杂度。

    比如说,如果用冒泡排序对数据排序,如果直接在原始数据上排,那么根本不需要额外的存储空间,而最多只需要定义几个变量,那么复杂度就是1

    如果排序产生一个新的数组,不修改原来的数组,那么对于排序n个数据,就需要n个新的存储空间,那么复杂度就是n。

    再比如,对于两个数组,求它们的笛卡儿积(比如a=1,2,3 b=a,b,结果是1a 1b 2a 2b 3a 3b),那么它的复杂度就是n^2

    更多相关内容
  • 算法复杂度分为时间复杂度和空间复杂度。 其作用: 时间复杂度是指执行算法所需要的计算工作量; 而空间复杂度是指执行这个算法所需要的内存空间。 (算法的复杂性体现在运行该算法时的计算机所需资源的多少上,...
  • 空间复杂度 常见时间复杂度对比 复杂度的OJ练习 什么是数据结构? 数据结构(Data Structure)是计算机存储、组织数据的方式。指相互之间存在一种或多种特定关系的数据元素的集合 什么是算法? 算法...

    目录

     

    什么是数据结构?

    什么是算法?

    算法效率

    如何衡量一个算法的好坏?

    算法的复杂度

    时间复杂度

    时间复杂度的概念

    大O的渐进表示法

    常见时间复杂度计算举例

    空间复杂度

    常见时间复杂度对比

    复杂度的OJ练习


    什么是数据结构?

    数据结构(Data Structure)是计算机存储、组织数据的方式。指相互之间存在一种或多种特定关系的数据元素的集合

    什么是算法?

    算法(Algorithm):就是定义良好的计算过程,他取一个或一组的值为输入,并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤,用来将输入数据转化成输出结果。

    算法效率

    如何衡量一个算法的好坏?

    如何衡量一个算法的好坏呢?比如对于下面的斐波那契数列:

    long long Fib(int N)
    {
      if(N<3)
       return 1;
     
    
    return Fib(N-1)+Fib(N-2);
    }

    斐波那契数列的递归实现方式非常的简洁,但是简洁就一定好嘛?那我们该如何衡量其好与坏呢?这就引出了我们下面要讲的内容。

    算法的复杂度

    算法在编写可执行程序后,运行时需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的,即时间复杂度与空间复杂度。

    时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度了。

    时间复杂度

    时间复杂度的概念

    时间复杂度的定义:在计算机科学中,算法的时间复杂度是一个函数(这个函数指的是数学里面带有未知数的函数表达式),它定量描述了该算法的运行时间。一个算法执行所耗费的时间,从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。但是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例,算法的基本操作的执行次数,为算法的时间复杂度

    即:找到某条基本语句与问题规模N之间的数学表达式,就是算出来该算法的时间复杂度。

    下面我们来举一个例子看看吧

    //请计算一下Func1中++count的语句总共执行了多少次?
    void Fun1(int N)
    {
      int count = 0;
      for(i=0;i<N;i++)
      {
        for(int j = 0;j<N;++j)
        {
          ++count;
        }
      }
    
    for(int k = 0;k<2*N;++k)
    {
       ++count;
    }
      int M = 10;
      while(M--)
      {
        ++count;
       }
    

    你认为它总共执行了多少次呢?

    Func1执行的次数:

    时间复杂度的函数式:F(N) = N^2+2*N+10;

    当N=10时,F(N) = 130

    当N=100时,F(N) = 10210

    当N=1000时,F(N) = 1002010

    通过结果我们可以看出,当N越大,后面2*N+10这两项对结果的影响就越小。

    实际上我们计算时间复杂度的时候,我们其实并不一定要计算精确的执行次数,而只需要大概的执行次数,那么这里我们使用大O的渐进表示法(估算

    上面代码的时间复杂度就是O(N^2)

    大O的渐进表示法

    大O符号(Big O notation):是用于描述函数渐进行为的数字符号。

    推导大O阶方法:

    1.用常数1取代运行时间中的所有加法常数。

    2.再修改后的运行次数函数中,只保留最高阶项。

    3.如果最高阶项存在且不是1,则取出与这个项目相乘的常数。得到的结果就是大O阶。

    这三点具体是什么意思呢?我们后面会用代码举例来介绍

    使用大O的渐进表示法后,上面Func1的时间复杂度为:O(N^2)

    通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项,简洁明了的表示出了执行次数。

    另外有些算法的时间复杂度存在最好、平均和最坏的情况:

    最坏情况:任意输入规模的最大运行次数(上界)

    平均情况:任意输入规模的期望运行次数

    最好情况:任意输入规模的最小运行次数(下界)

    比如说:在一个长度为N的数组中搜索一个数据x

    最好情况:1次找到

    平均情况:N/2次找到

    最坏情况:N次找到

    常见时间复杂度计算举例

    实例1:

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

    你认为这段代码的时间复杂度是多少呢?

    精确的是:F(N) = 2N+10

    用大O渐进表示法来表示的话这段代码的时间复杂度就是O(N)

    为什么呢?

    当N无限大的时候这个10对于结果的影响就很小,并且由推导大O阶方法的第三点可知如果最高阶项存在且不是1,则去除与这个项目的常数,因此时间复杂度就是O(N)。

    实例2:

    //计算Fun3的时间复杂度
    void Fun3(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);
    }

    你认为这段代码的时间复杂度是多少呢?

    这段代码的时间复杂度用大O渐进表示法是O(M+N)

    原因:第一个for循环执行了N次,第二个for循环执行了M次,由于这里的N与M都是未知数,不知道谁大谁小,因此是O(M+N)。

    一般情况下时间复杂度计算时未知数都是用的N,但是也可以用M,K等等其他的。

    如果这道题说了N>>M,那么时间复杂度就是O(N)

    如果M>>N,那么时间复杂度就是O(M).

    实例3:

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

    你认为这段代码的时间复杂度是多少呢?

    由于这里的循环执行了100次是常数次,由推导大O阶方法第1点可知用常数1取代运行时间中的所有加法常数。

    所以这段代码的时间复杂度是O(1),注意这里的O(1)不是代表算法运行一次,而是常数次

    实例4:

    //计算strchar的时间复杂度
    const char* strchr(const char* str, int character);
    
    
    strchr的大概写法
    //相当于是在一个字符串中找一个字符
    while(*str)
    {
       if(*str == character)
          return str;
          else
          ++str;
    }

    你认为这段代码的时间复杂度是多少呢?

    对于这个代码我们就需要分情况:

     当一个算法随着输入不同,时间复杂度不同,时间复杂度做悲观预期,看最坏的的情况

    因此我们这段代码的时间复杂度是O(N)

    实例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;
    	}
    }

    你认为上面这段冒泡排序的时间复杂度是多少呢?

    精确的是:F(N) = N-1+N-2+N-3+...+N-i+1=0 = N*(N-1)/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)
    			begin = mid;
    		else
    			return mid;
    	}
    	return -1;
    }

    你认为这个二分查找代码的时间复杂度是多少呢?

    O(N)嘛?我相信很多人就光看这里的循环执行次数肯定会认为是O(N)

    因此通过这个例子我想告诉大家:

    算时间复杂度不能只去看是几层循环,而是要去看他的思想

    那么我们怎么来理解这个算法的思想呢?

    我们拿出一张纸,把他折成长方形的样子,假设这张纸就是我们的一个有序数组,我们要在这个数组里面找某个值。我们先从中间的位置开始找,如果我们要找的值比中间的值大那么就从中间的右边开始找,将我们的纸对折一次,这样我们搜索的区域就变成原来搜索区域的一半了。我们继续从中间开始找,假设现在要找的值还是比中间的值要大,我们再将纸对折一次,依此类推直到找到或者找不到为止

    因此这个代码的时间复杂度是O(log2^N)

    二分查找算法其实是一个非常牛逼的算法

    N个数中查找              大概查找次数

    1000                              10

    100w                              20

    10亿                               30

    但前提是这N个数得是有序的

    实例7:

    //计算阶乘递归Fac的时间复杂度
    long long Fac(size_t N)
    {
    	if (0 == N)
    		return 1;
    	
    	return Fac(N - 1)*N;
    }

    你认为这段代码的时间复杂度是多少呢?

    这段代码的时间复杂度是O(N)

    递归算法:递归次数*每次递归调用的次数

    这里递归了n次,每次递归调用的次数是常数次(我们就认为它是O(1)

    因此这段代码的时间复杂度是O(N) 

    实例8:

    //计算斐波那契数列Fib的时间复杂度
    long long Fib(size_t N)
    {
    	if (N < 3)
    		return 1;
    
    	return Fib(N - 1) + Fib(N - 2);
    
    }

    这段代码的时间复杂度又是多少呢?

    它的时间复杂度是O(2^N)

    斐波那契数列的递归调用有点像二叉树,也有点像我们生物上面的细胞分裂。

    上面的X是递归过程中一些递归分支提前结束的那部分

    通过等比数列公式我们可以求得Fib(N) = 2^N -1

    因此斐波那契数列的时间复杂度是O(2^N)

    总结:当一个算法分多种情况时,时间复杂度取它的最坏情况。通过以上例子我们就可以知道,求一个算法时间复杂度的时候,不能够单单看循环的次数来认定它的时间复杂度,而是应该去看这个算法的思想进行层层分析最后得到它的时间复杂度

    空间复杂度

    空间复杂度也是一个数学表达式,是对一个算法再运行过程中临时额外占用存储空间大小的量度

    空间复杂度不是程序占用了多少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(N)吗?

    这段代码的空间复杂度是O(1),很多人可能会这么认为:这段代码在第一层循环里面定义了end,然后在第二层循环里面定义了n个i变量,所以是O(N).但其实不是这样的。

    在冒泡排序的函数栈帧中,会先定义一个end,再定义一个i,第二层循环结束后i销毁,再循环上来又会创建一个i,但是这里的i与之前的i是共用同一块空间的。这个代码额外使用了三个(再加上change)空间,也就是常数个,所以它的空间复杂度是O(1)

    注意:空间是可以重复利用的,不累计的。时间是一去不复返,累计的

    实例2:

    //计算Fibonacci的空间复杂度
    //返回斐波那契数列的前n项
    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;
    }

    你认为这段代码的空间复杂度是多少呢?

    这段代码的空间复杂度是O(N)

    我们在这里动态开辟了一个n+1个long long空间大小的数组,然后又定义了i变量。

    因此它空间复杂度是O(N).

    下面我们再来看一个例子吧

    实例3:

    //计算阶乘递归Fac的空间复杂度
    long long Fac(size_t N)
    {
    	if (N == 0)
    		return 1;
    
    
    	return Fac(N - 1)*N;
    }

    你认为这段代码的空间复杂度又是多少呢?

    它的空间复杂度是O(N)

    递归算法的空间复杂度要看栈帧的消耗--递归的深度

    这段代码调用了N次,由于每次调用都会创建栈帧,我们可以认为每次建立的栈帧中有常数个变量,由于建立了N次,因此这里的空间复杂度是O(N)

    实例4:

    //计算斐波那契数列Fib的空间复杂度
    long long Fib(size_t N)
    {
    	if (N < 3)
    		return 1;
    
    	return Fib(N - 1) + Fib(N - 2);
    
    }

    你认为斐波那契数列的空间复杂度是多少呢?

    这段代码的空间复杂度是O(N)

    结合上面时间复杂度的那副图把它递归层层展开的时候开辟的栈帧当作是一个结点,每创建一个结点都是依次函数调用。还是上面那句话:时间是一去不复返的,累积的。空间是可以重复利用的,不累计的。每次递归调用,当Fib(N)递归完了,就会就它申请的内存还给操作系统,然后Fib(N-1)才开始递归依此类推,最多建立了N个栈帧,并且他们用的是同一块空间。

    简单来说就是:当Fib(N)开始递归的时候,会建立N个栈帧,当它递归完了之后,就把它申请的内存归还给操作系统,然后Fib(N)递归完了,Fib(N-1)才开始递归,它会建立N-1个栈帧,它所申请的内存空间就是之前Fib(N)还给操作系统的那块内存空间,重复利用

    因此它的空间复杂度是O(N)

    常见时间复杂度对比

    5201314O(1)常数阶段
    3n+4O(n)线性阶
    3n^2+4n+5O(n^2)平方阶
    3log(2)n+4O(logn)对数阶
    2n+3nlog(2)n+14O(nlogn)

    nlogn阶

    n^3+2n^2+4n+6O(n^3)立法阶
    2^nO(2^n)指数阶

    复杂度的OJ练习

    上面举了那么多时间复杂度与空间复杂度的例子。下面我们就来做几道题练练手吧

    题目链接:面试题 17.04. 消失的数字

    题目描述:

    数组nums包含从0n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗?

    思路1:利用快速排序然后遍历数组看后一个数是不是前一个数+1,如果是的话就找到了。

    时间复杂度是O(N*logN) 不符合题目的要求

    思路2:通过一个循环求出1+2+3+....+到n的值,再通过一个循环求出数组中每个值相加的和

    再用第一个循环求出的值减去第二个循环求出的值,那么得到的值就是缺失的数字。时间复杂度是O(N)满足要求

    思路3:建立一个n+1空间大小的数组,将数组的值写到该数组下标对应的位置上,哪个位置没有写那么这个数就是缺失的数字。时间复杂度O(N) 空间复杂度就变成了O(N) 这种方法就是拿空间换时间。

    思路4:给一个值x=0 然后将x与0到n的所有值异或,x再跟数组中的每个值异或,最后x就是却的那个数字。这里就借助了异或的特性:相异为1,相同为0,0跟任何数异或的值就是另外一个数

    //思路4:
    int missingNumber(int* nums, int numsSize){
    int x = 0;
    int i = 0;
    for(i=0;i<numsSize+1;i++)
    {
         x^=i;
    }
    for(i=0;i<numsSize;i++)
    {
        x^=nums[i];
    }
    return x;
    }

    题目链接:189. 旋转数组

    题目描述:

    给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

    输入: nums = [1,2,3,4,5,6,7], k = 3
    输出: [5,6,7,1,2,3,4]
    解释:
    向右旋转 1 步: [7,1,2,3,4,5,6]
    向右旋转 2 步: [6,7,1,2,3,4,5]
    向右旋转 3 步: [5,6,7,1,2,3,4]

    思路1:暴力求解,旋转K次,时间复杂度O(N*K),空间复杂度O(1)

    思路2:开辟额外空间,旋转K次就是将数组中后K个的数拷到新开辟的空间中,再把数组前n-k个数拷到新开辟的空间中去,然后再将新数组中的值拷回到原来的数组中去,以空间换时间。时间复杂度O(N),空间复杂度O(N)

    思路3:先将数组中前n-k个数进行逆置,再将数组中后k个数进行逆置,最后再将数组中的数进行整体逆置。时间复杂度O(N),空间复杂度O(1)

    //思路3
    void Reverse(int*nums,int left,int right)
    {
       while(left<right) 
       {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
        left++;
        right--; 
       }
    }
    
    void rotate(int* nums, int numsSize, int k){
        if(k>=numsSize)
        {
            k%=numsSize;
        }
    
    //前n-k个数逆置
    Reverse(nums,0,numsSize-k-1);
    //后k个数逆置
    Reverse(nums,numsSize-k,numsSize-1);
    //整体逆置
    Reverse(nums,0,numsSize-1);
    }

    以上就是本篇文章的全部内容了,如果对文章内容感兴趣的可以给作者三连(点赞关注收藏)一波哦。

    展开全文
  • 指针不算入空间复杂度?两个指针o(1)吗 指针不算入空间复杂度?两个指针o(1)吗 指针不算入空间复杂度?两个指针o(1)吗
  • 一、空间复杂度定义 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。 一个算法在计算机存储器上所占用的存储空间,包括程序代码所占用的空间,输入数据所占用的空间和辅助变量所...

    一、空间复杂度定义

    空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。
    一个算法在计算机存储器上所占用的存储空间,包括程序代码所占用的空间输入数据所占用的空间辅助变量所占用的空间这三个方面。

    二、影响空间复杂度的因素

    在这里插入图片描述
    注意:
    一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小,它包括为参数表中形参变 量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。若一个算法为递归算法,其空间复杂度为递归所使用的堆栈空间的大小。它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1,这个1表示开始进行的一次非递归调用)
    递归的空间复杂度: 每次递归所开空间*深度。

    算法在运行过程中临时占用的存储空间讲解:
    1、有的算法只需要占用少量的临时工作单元,而且不随问题规模的大小而改变,我们称这种算法是“就地”进行的,是节省存储的算法,下面会介绍。

    2、有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,当n较大时,将占用较多的存储单元,例如快速排序和归并排序算法就属于这种情况。

    三、计算方法
    ①忽略常数,用O(1)表示
    ②递归算法的空间复杂度=递归深度n*每次递归所要的辅助空间
    ③对于单线程来说,递归有运行时堆栈,求的是递归最深的那一次压栈所耗费的空间的个数,因为递归最深的那一次所耗费的空间足以容纳它所有递归过程。

    四、例子

    1、空间算法的常数阶
    在这里插入图片描述
    如上图,这里有三个局部变量分配了存储空间,所以f(n) = 1 + 1 + 1 = 3,根据上面的法则该函数不受n的影响且为常数项,所以空间复杂度记作O(1)。这种与问题的大小无关(n的多少),执行时间恒定的算法,我们称之为具有O(1)的空间复杂度,又叫常数阶。

    2.空间算法的线性阶(递归算法)
    在这里插入图片描述
    如上图,这是一个递归算法(计算从n + (n-1) + (n-2) + … + 2 + 1的和)
    每当执行一次该函数就会为tmp分配一个临时存储空间,所以f(n) = 1*(n-1+1) = n,函数是受n影响的所以空间复杂度记为O(n)。

    3、二分查找分析

    在这里插入图片描述

    方法一(迭代法):

    /// <summary>
    /// 二分查找
    /// </summary>
    /// <param name="arr">查找数组</param>
    /// <param name="len">数组长度</param>
    /// <param name="num">查找项</param>
    /// <returns></returns>
    int BinarySearch(int[] arr,int len,int num)
    {
        int left = 0;
        int right = len - 1;
        int mid;
        while (left <= right)
        {
            mid = (left + right) / 2;
            if (arr[mid] > num)
                right = mid - 1;
            else if (arr[mid] < num)
                left = mid + 1;
            else
                return mid;
        }
        return -1;
    }
    

    时间复杂度:
    left、right、mid运算次数
    f(n1) = 1 + 1 + 1 = 3
    我们将While循环中的运算作为一个整体看待,每次都是折半运算次数
    f(n2) = log2^n
    总运行次数
    f(all) = f(n1)+f(n2) = 3 + log2 ^ n
    时间复杂度记为:O(log2^n)


    空间复杂度:
    算法中left、right、mid只创建的次数
    s(n) = 1 + 1 + 1 = 3
    空间复杂度记为:O(1)


    方法二(递归法):

     /// <summary>
    /// 二分查找(递归法)
    /// </summary>
    /// <param name="arr"></param>
    /// <param name="left"></param>
    /// <param name="right"></param>
    /// <param name="num"></param>
    /// <returns></returns>
    int BinarySearchRecursion(int[] arr,int left,int right,int num)
    {
        int mid = (left + right) / 2;
        if (left <= right)
        {
            if (arr[mid] > num) {
                right = mid - 1;
                return BinarySearchRecursion(arr,left,right,num);
            }
            else if (arr[mid] < num)
            {
                left = mid + 1;
                return BinarySearchRecursion(arr,left,right,num);
            }
            else
                return mid;
        }
        else
        {
            return -1;
        }
    }
    

    时间复杂度:
    运行次数 f(n) = log2 ^ n
    时间复杂度记为:O(log2^n)


    空间复杂度:
    因为整个算法中mid只创建的次数
    s(n) = log2 ^ n
    空间复杂度记为:O(log2 ^ n)


    4、斐波那契数列

    斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……
    这个数列从第3项开始,每一项都等于前两项之和。

    如果设F(n)为该数列的第n项(n∈N*),那么这句话可以写成如下形式::F(n)=F(n-1)+F(n-2)

    显然这是一个线性的递推数列。
    通项公式 :
    在这里插入图片描述
    上面就是斐波那契数列的递推公式,这样一个完全是自然数的数列,通项公式却是用无理数来表达的。而且当n趋向于无穷大时,前一项与后一项的比值越来越逼近黄金分割0.618
    在这里插入图片描述
    递推是公式是求解斐波那契数列的一个方法,我们当然也可以用计算机编写程序来求解。

    方法一(迭代法):

    /// <summary>
    /// 斐波那契(迭代法)
    /// </summary>
    /// <param name="n"></param>
    /// <returns></returns>
    int Fibonacci(int n)
    {
        if (n <= 0)
            return -1;
        if (n == 1 || n == 2)
            return 1;
        else
        {
            int num = 0;
            int a = 1;
            int b = 1;
            while (n - 2 > 0)
            {
                num = a + b;
                a = b;
                b = num;
                n--;
            }
            return num;
        }
    
    }
    

    时间复杂度:
    while以外的算法语句都忽略不计(不随n的变化而变化)
    while算法语句所有语句
    f(n) = 4 *(n - 2) = 4n - 8
    时间复杂度记为:O(n)


    空间复杂度:
    算法中num、a、b只创建1次
    s(n) = 1 + 1 + 1 = 3
    空间复杂度记为:O(1)


    方法二(递归法):

    /// <summary>
    /// 斐波那契(递归法)
    /// </summary>
    /// <param name="n"></param>
    /// <returns></returns>
    int FibonacciRecursion(int n)
    {
        if (n <= 0)
            return -1;
        if (n == 1 || n == 2)
            return 1;
        return FibonacciRecursion(n - 1) + FibonacciRecursion(n - 2);
    }
    

    时间复杂度:
    递归调用的形参有两个n - 1 和 n - 2
    时间复杂度记为:O(2^n)


    空间复杂度:
    递归的空间复杂度 =(n + 1)* 调用的深度
    空间复杂度记为:O(n)(这里可以简单的根据二叉树的层来进行计算)


    展开全文
  • 时间复杂度和空间复杂度算法效率时间复杂度大O渐进表示法(估算)空间复杂度 什么是数据结构? 数据结构(Data Structure)是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。 什么是...

    数据结构

    数据结构中有简单存储数据的存储结构,比如顺序表、链表、串。不仅仅要存储数据、存起来还要查找数据,比如搜索树、哈希表等等这样结构。在写通讯录中,存储联系人信息我们可以用顺序表(数组)存储或者链表。

    什么是数据结构?

    数据结构(Data Structure)是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。

    什么是算法?

    算法是指解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。通过某种处理得到结果。数据结构和算法是不分家,数据结构中包含一些算法,一些算法的解决又离不开数据结构

    如何学好数据结构呢?

    • 勤加练习,多敲代码

    image-20210728214845562

    时时刻刻敲代码,你就成功学好了。哈哈哈哈,开个玩笑,反正需要勤加练习多做题

    • 多画图,多分析

    数据结构的逻辑思想十分重要,所以我们需要多画图来便于我们理解与分析。

    推荐的书籍与做题地方:《剑指offer》、leetcode

    时间复杂度和空间复杂度

    算法效率

    如何衡量一个算法的好坏?

    复杂度计算:时间效率和空间效率,算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度。时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外空间。

    在算法效率这一方面我们只需要重点关注时间复杂度。

    硬件发展:摩尔定律

    摩尔定律是英特尔创始人之一戈登·摩尔的经验之谈,其核心内容为:集成电路上可以容纳的晶体管数目在大约每经过18个月便会增加一倍。换言之,处理器的性能每隔两年翻一倍。

    每过18个月,硬件性能就能提升一倍,随着计算机的发展,我们的运行设备现在内存越来越大,所以我们不再特别关注空间复杂度。

    时间复杂度

    算法的时间复杂度是一个函数(数学中的函数),==算法中的基本操作的执行次数为算法的时间复杂度,时间复杂度不是去计算准确时间的,因为我们是没办法准确的计算时间的,比如说冒泡排序,对10w个数字排序,在一台最新酷睿i7和8g内存电脑上可能很快,在一台10年前i3和2g电脑上可能慢很多,算法要计算准确的时间,需要跟运行环境有关。

    即找到某条基本语句与问题规模N之间的数学表达式,就是算出了该算法的时间复杂度。

    例1:

    // 请计算一下Func1中++count语句总共执行了多少次?
    void Func1(int N)
    {
    	int count = 0;
        for (int i = 0; i < N ; ++ i)
        {
            for (int j = 0; j < N ; ++ j)
            {
            	++count;
            }
       	}
    }
    for (int k = 0; k < 2 * N ; ++ k)
    {
        ++count;
    }
        int M = 10;
        while (M--)
        {
            ++count;
        }
    

    首先写出算法的时间复杂度函数:

    F(N)=N*N+2*N+10

    N = 10时 F(N) = 130
    N = 100时 F(N) = 10210
    N = 1000时 F(N) = 1002010

    我们发现后两项,N越大,对结果影响越小,实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,那么这里我们使用大O的渐进表示法。

    大O渐进表示法(估算)

    大O符号(Big O notation):是用于描述函数渐进行为的数学符号

    大O的渐进表示法:

    1、用常数1取代运行时间中的所有加法常数。
    2、在修改后的运行次数函数中,只保留最高阶项。
    3、如果最高阶项存在且系数不是1,则去除与这个项的系数。得到的结果就是大O阶。

    所以在复杂度中1不是代表1次,代表常数次。

    保留对结果影响最大的一项(次数最高的一项),去掉系数。

    有些算法的时间复杂度存在最好、平均和最坏情况:

    最坏情况:任意输入规模的最大运行次数(上界)
    平均情况:任意输入规模的期望运行次数
    最好情况:任意输入规模的最小运行次数(下界)

    例如:在一个长度为N数组中搜索一个数据x

    最好情况:1次找到
    最坏情况:N次找到
    平均情况:N/2次找到

    而时间复杂度关注最坏的情况,用最坏去衡量这样的算法,用最坏是靠谱的,这个算法一定不会比这个更差了。

    例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);
    }
    

    O(M+N)或者O(max(M,N))

    当M和N相差不大时,O(M)和O(N)都可以

    如果能说明M远大于N,就是O(M)

    如果能说明N远大于M,就是O(N)

    例3:

    // 计算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);
    }
    

    时间复杂度函数:2*N+10,时间复杂度:O(N).

    例4:

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

    时间复杂度函数为:F(N)=100,根据大O阶法,时间复杂度为:O(1)。

    例5:

    // 计算strchr的时间复杂度?
    const char * strchr ( const char * str, int character )
    {
        if(*str==character)
        {
            return *str;
        }
        else
        {
            str++;
        }
    }
    

    假设字符串长度为N:

    最坏情况:N次

    最好情况:1次

    平均情况:N/2

    用最坏情况是衡量这样的算法,用最坏是靠谱的,因为这个算法一定不会比这个更差了。

    例6:

    // 计算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;
        }
    }
    

    很显然这是一个冒泡排序

    end等于n时,里面的循环需要进行n次判断,end等于n-1时,里面的循环需要进行n-1次判断,依此类推,可以得到时间复杂度函数。

    准确次数复杂度函数:

    *F(N)=N+N-1+N-2+…+2+1=(N+1)N/2

    F(N)=N^2/2+N/2

    时间复杂度:O(N)=N^2

    例7:

    // 计算BinarySearch的时间复杂度?
    int BinarySearch(int* a, int n, int x)
    {
        assert(a);
        int begin = 0;
        int end = n-1;
        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;
    }
    

    二分查找时间复杂度

    最坏情况下的时间复杂度是:一直折半查找,直到折半到只剩一个数字的时候,要么这个数字是查找的数字,要么不是,就查找结束了

    所以我们查找一次,N折半一次,所剩范围相当于N/2,查找X次,我们N/2^X,直到结果为1。找了多少次就要折半多少次

    即:N/2/2/2/2…/2 = 1

    假设找了X次,即:N/2^X=1

    则:N=2^X

    即:X=log2N

    算法里面很多时候,如果不是编辑器支持,不好敲底数,所以一般情况复杂度计算,可以把log2N简化成logN,有不少书上或者网上的资料还喜欢简化为O(lgN),严格来说这个是不对,因为跟数学中就混了,所以注意不要这样写,但是如果别人写了,我们也要知道那其实是log2N

    所以二分查找的时间复杂度为O(N)=log2N

    例8:

    // 计算阶乘递归Fac的时间复杂度?
    long long Fac(size_t N)
    {
        if(1 == N)
        	return 1;
        return Fac(N-1)*N;
    }
    

    递归算法时间复杂度如何计算呢?

    每次递归的累积次数相加

    image-20210726213253006

    n个1次相加是N次,所以算法时间复杂度为O(N)。

    例9:

    // 计算斐波那契递归Fib的时间复杂度?
    long long Fib(size_t N)
    {
        if(N < 3)
        	return 1;
        return Fib(N-1) + Fib(N-2);
    }
    

    image-20210726215352252

    函数递归调用如上图所示,一共有2^N-1个调用,每次递归调用执行的次数为1,故时间复杂度为O(N)=2^N。

    一般算法常见的复杂度如下:

    image-20210726215814660

    image-20210726215802911

    我们发现O(1)和O(logn)的时间复杂度相近,这两个相较于其他是最优的,O(2^n)的时间复杂度,可由曲线可见,增长速度很快,所以这种时间复杂度的代码一般是不行的。

    空间复杂度

    空间复杂度也是一个数学表达式,是对一个算法在运行过程中临时占用存储空间大小的量度
    空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。
    空间复杂度计算规则基本跟实践复杂度类似,也使用大O渐进表示法。
    注意:函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

    注意:

    时间是累积的,而空间是不累积的(可以重复利用)

    // 计算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(1)

    额外开辟的空间的空间复杂度:

    // 计算Fibonacci的空间复杂度?
    // 返回斐波那契数列的前n项
    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;
    }
    

    空间复杂度:O(N)

    // 计算阶乘递归Fac的空间复杂度?
    long long Fac(size_t N)
    {
        if(N == 0)
        	return 1;
        return Fac(N-1)*N;
    }
    

    递归调用N个函数会开辟N个函数栈帧,每一个函数都是O(1),N个这样的函数就是O(N)

    // 计算斐波那契递归Fib的空间复杂度?
    long long Fib(size_t N)
    {
        if(N < 3)
        	return 1;
        return Fib(N-1) + Fib(N-2);
    }
    

    image-20210726215352252

    时间是累积的,空间是不累积的(可以重复利用),我们在递归调用时,在开始调用时,我们一直调用到fib(2)时函数开始返回,函数只要一返回,空间就释放掉了,而fib N到fib 2一共创建了N-1个函数栈帧,因为函数在返回时,就释放还给操作系统了,所以这段代码最多用了N-1个函数栈帧,一个函数的空间复杂度为O(1),这N-1个就为O(N-1),又根据大O阶法,所以空间复杂度为:O(N)

    展开全文
  • 目录算法效率时间复杂度概念大O的线性表示法时间复杂度举例空间复杂度空间复杂度的定义空间复杂度举例 时间复杂度与空间复杂度是用来分析一个算法的效率的。 算法效率 算法效率分析分为两种:第一种是时间效率,第二...
  • 时间复杂度与空间复杂度该怎么?这里一站式搞定!
  • 忽略常数,用O(1)表示递归算法的空间复杂度=递归深度N*每次递归所要的辅助空间对于单线程来说,递归有运行时堆栈,求的是递归最深的那一次压栈所耗费的空间的个数,因为递归最深的那一次所耗费的空间足以容纳它所有...
  • 算法空间复杂度详细介绍
  • 时间复杂度和空间复杂度前言算法效率时间复杂度1.时间复杂度的概念2.大O的渐进(估算)表示法推导大O阶方法(重点!!!):另外有些算法的时间复杂度存在最好、平均、和最坏情况(重点!!!):3.常见时间复杂度计算...
  • 时间复杂度和空间复杂度详解

    千次阅读 2021-03-29 14:47:12
    时间复杂度和空间复杂度详解 目录1.算法效率2.时间复杂度3.空间复杂度 1.算法效率 算法效率分析分为两种:第一种是时间效率,第二种是空间效率。时间效率被称为时间复杂度,而空间效率被称作空间复杂度。 时间复杂度...
  • 一般算法的空间复杂度相信大家已经都掌握了 那么大家想一想递归算法的空间复杂度应该怎么分析呢。 我这里用一个到简单的题目来举例 题目:求第n的斐波那契数 相信使用递归算法来求斐波那契数,大家应该再熟悉不过了 ...
  • 1. 算法效率 ...在计算机才初步发展的年代,计算机的存储容量非常小,人们对算法空间复杂度的重视程度远远大于时间复杂度,但随着计算机技术的迅速发展,计算机的内存容量已经有了非常大的提高,所以现在
  • 算法的时间复杂度和空间复杂度

    千次阅读 2022-03-09 18:56:06
    空间复杂度 常见时间复杂度以及复杂度oj练习 一. 算法的效率 1. 如何衡量一个算法的好坏 如何衡量一个算法的好坏呢?比如对于以下斐波那契数列: long long Fib(int N) { if(N < 3) return 1; return...
  • 时间复杂度计算及空间复杂度计算

    多人点赞 热门讨论 2021-10-10 14:54:27
    空间复杂度4.大O渐进表示法5.常见时间复杂度 1.算法效率 算法效率分析分为两种:第一种是时间效率,第二种是空间效率。时间效率被称为时间复杂度,而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的...
  • 类似于时间复杂度的讨论,一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间,它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度空间复杂度(Space Complexity)是对一个算法在...
  • 递归的时间复杂度三、空间复杂度1.空间复杂度概念2.空间复杂度的计算(1) 冒泡排序(2) 斐波那契数列(3)递归总结 一、算法效率 算法效率分析分为两种:第一种是时间效率,第二种是空间效率。时间效率被称为时间复杂度...
  • 时间复杂度和空间复杂度 1:什么是数据结构 数据结构(Data Structure)是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合 2:什么是算法 算法(Algorithm):就是定义良好的计算过程...
  • 时间效率被称为时间复杂度,而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要的额外空间,在计算机发展的早期,计算机的存储容量很小。所以对空间...
  • 时间复杂度和空间复杂度 如何计算?

    万次阅读 多人点赞 2019-01-23 11:55:29
    时间复杂度和空间复杂度 如何计算?推导算法:大O推导法时间复杂度定义常数阶线性阶对数阶平方阶小结空间复杂度定义 推导算法:大O推导法 1、用常数1取代运行时间中的所有加法常数 2、在修改后的运行次数函数中,只...
  • ⭐前言⭐复杂度时间复杂度概念的引出实战分析线性常数阶平方阶二分查找对数阶及证明递归线性指数爆炸空间复杂度概念的引出实战分析循环重复创建变量递归线性????结尾语???? ⭐前言⭐ 本文将要介绍数据结构的开篇–...
  • 文章目录1.算法效率2.时间复杂度大O渐近表示法3.空间复杂度 1.算法效率 算法效率分析分为两种:第一种是时间效率,第二种是...计算时间复杂度和空间复杂度时,为了估算一个算法的耗时情况,不需要计算出精确的执行次
  • 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要的额外空间. 2.时间复杂度 2.1 时间复杂度的概念 时间复杂度的定义:在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该...
  • 数据结构:空间复杂度

    千次阅读 多人点赞 2021-09-10 13:03:17
    空间复杂度
  • 算法复杂度分为时间复杂度和空间复杂度。其作用: 时间复杂度是度量算法执行的时间长短;而空间复杂度是度量算法所需存储空间的大小。1、时间复杂度1.1 时间频度一个算法中的语句执行次数称为语句频度或时间频度。记...
  • 数据结构>时间复杂度及空间复杂度

    多人点赞 热门讨论 2022-03-03 23:08:11
    1.3、空间复杂度 二、计算 2.1、大O的渐进表示法 2.2、时间复杂度计算 例题: 2.3、空间复杂度计算 例题 三、有复杂度要求的习题 一、概念 1.1、算法效率 算法效率分析分为两种:第一种是时间效率...
  • 空间复杂度(Space Complexity)记作S(n) 依然使用大O来表示利用程序的空间复杂度,可以对程序运行时所需要多少内存有个预先估计。我这里来回答两个常见的相关问题空间复杂度是考虑程序(可执行文件)的大小么?...
  • 算法的时间复杂度和空间复杂度计算

    万次阅读 多人点赞 2018-09-27 20:22:44
    1、算法时间复杂度 1.1算法时间复杂度的定义:  在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度,记作...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 71,144
精华内容 28,457
关键字:

空间复杂度怎么算

友情链接: 1.zip