时间复杂度例题

N){if(N…各位少年大家好我是那一脸阳光本次分享的主题是时间复杂度和空间复杂度

时间复杂度例题

我们发现每次FIbN开始每次递归都变成两个然后通过错位即可算出

https://leetcode-cn.com/problems/missing-number-lcci/

数组nums包含从0到n的所有整数但其中缺了一个。

请编写代码找出那个缺失的整数。

你有办法在O(n)时间内完成吗

{int

22也是0大家注意第二个循环即可这种题一般非常的简单的0a都是0

如果对这里不太懂

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

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

注意函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因

c//

0)break;冒泡排序的时间复杂度在ON^2),空间复杂度是O1因为这个没有额外消耗或者有代码创造变量。

long

fibArray这段代码时间复杂度是ON空间复杂度也是ON因为这里的动态内存分配开辟了n1个空间。

例子一

Fac(N-1)*N;}这里的每次递归都在栈中创建空间每次递归都会创建一定的空间所以空间复杂度是ON。

常见复杂度对比

前三段逆置后四个再逆置最后整体逆置但是这种方法一般人能不出来所以还有其他方法这段代码时间复杂度是ON^2)空间复杂度是O1这里接受另外一种写法

再开创一个tmp数组然后再把tmp数组拷贝到a数组里头然后销毁tmp数组即可这样以空间换时间的方法。

这道题中三段逆置最优其次就是空间换时间这种方法是最优的但空间复杂度会上涨到ON

void

tmpa[left];a[left]a[right];a[right]tmp;left--right;}}void

rotate(int*nums,int

k)ifknumsSize)k%numsSize;reverse(nums,0,numsSize-k-1);reverse(nums,numsSize-k,numsSize-1);reverse(nums,0,numsSize-1);}这段代码完成了

void

int*tmp(int*)malloc(sizeof(int)*numsSize);

memcpy(tmpk,nums,sizeof(int)*(numsSize-k);

memcpy(tmp,numsnumsSize-k,sizeof(int*k)

memcpy(nums,tmp.sizeof(int)*(numsSize));

free(tmp);

线性表在逻辑上是线性结构也就说是连续的一条直线。

但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。

数组长度

静态顺序表只适用于确定知道需要存多少数据的场景。

静态顺序表的定长数组导致N定大了空间开多了浪

费开少了不够用。

所以现实中基本都是使用动态顺序表根据需要动态的分配空间大小所以下面我们实现动态顺序表

我们实现一下

(SLDatatype*)malloc(sizeof(SLDatatype)*4);if

(psl-a

x;//psl-size;SLCheckCapacity(psl);psl-a[psl-size]

}void

释放空间然后通过数组进行尾部插入这里只实现了最简单的尾插。

剩下部分

我给大家写出来

6);SLPrint(s);SLDestroy(s);return