数据结构中时间复杂度和空间复杂度,数据结构怎么看时间复杂度
目录算法的效率算法的复杂度和时间复杂度都很大。o渐进式表示的常见时间复杂度计算示例：空间复杂度汇总
算法的效率。现在先不急着谈算法的效率。我们来想象一个场景：有一个很有味道的大学生，开了一个叫利口的网站刷题，随便眼花缭乱了一个问题，花了几十分钟功夫写了一个代码，点击运行，运行时间1001ms。他直接超时，当场死亡。然后缝缝补补，换个bug，一天就过去了。
这还是一个很优秀的大学生。大学生觉得自己刷题的策略很有问题，所以每道题做之前都会花几分钟思考一下：这道题你以前见过吗？有没有更好的解决办法？要不要考虑一些复杂的情况？虽然这个大学生还是很有味道的，但是他的做题经验提高了很多：省去了一些微调代码的时间，代码变得更好看了，准确率提高了很多，也有时间闲逛了。简单来说，他刷题的效率提高了。
既然题目是算法效率，那接下来就要说说算法了。以一个简洁漂亮的斐波那契数列为例。
长纤维(整数)
{
if(N ^ 3)
返回1；
返回光纤(N-1)光纤(N-2)；
}复杂的函数只需要几行代码就可以实现，但众所周知，这个函数在寻找40左右的斐波那契数时有些力不从心，更别说谈100，200了。
40左右，我能算出来。你需要什么？
为什么会这样？这和算法的复杂度有关。
算法的复杂度算法被写入可执行程序后，需要时间和空间(内存)资源来运行。所以一个算法的好坏一般从时间复杂度和空间复杂度两个维度来衡量。
时间复杂度主要衡量算法运行的速度，空间复杂度主要衡量算法运行需要的额外空间。
在计算机发展的早期，计算机的存储容量非常小。所以我非常关心空间的复杂性。然而，随着计算机行业的快速发展，计算机的存储容量已经达到了很高的水平。所以现在我们不需要特别关注一个算法的空间复杂度。
时间复杂度的定义：在计算机科学中，算法的时间复杂度是定量描述算法运行时间的函数。理论上，一个算法执行的时间是无法计算的。只有把你的程序放到机器上运行，你才能知道。但是我们需要在电脑上测试每一个算法吗？可以在电脑上测试，但是很麻烦，于是就有了时间复杂度分析法。算法花费的时间与其语句的执行次数成正比，算法中基本运算的执行次数就是算法的时间复杂度。
也就是说，找到一个基本句子和问题规模N之间的数学表达式，就是计算算法的时间复杂度。
例如：
//请计算一下Func1中的count语句总共执行了多少次？
void Func1(int N)
{
int count=0；
for(int I=0；I N；我)
{
for(int j=0；j N；j)
{
数数；
}
}
for(int k=0；k ^ 2 * N；k)
{
数数；
}
int M=10
while (M -)
{
数数；
}
printf(%d\n ，count)；
} func 1执行的基本操作数：
F(N)=N^2 2*N 10
当n的值很大时，后面几项对结果的影响越来越小。因此，我们实际上不必计算精确的执行时间，而只需要大概的执行时间。然后这个
我们在书中使用大O的递进式表示。
O大O符号：用来描述函数渐进行为的数学符号。
高阶方法的推导：
用常数1替换运行时的所有加法常数。在操作次数的修正函数中，只保留最高阶项。如果最高阶项存在且不为1，则删除乘以该项的常数。结果就是大O阶。使用大O的渐进表示后，Func1的时间复杂度为O(n ^ 2)
o的大型渐进表示法去掉了那些对结果影响很小的项，只显示了执行次数。
此外，一些算法具有最佳、平均和最差的时间复杂度：
最坏情况：任何输入标度的最大运行次数(上限)；平均情况：任何输入规模的预期运行次数；最佳情况：任何输入标度的最小运行次数(下限)；例如：在长度为n的数组中搜索数据x。
最好的情况：一次找到最坏的情况：N次找到一般的情况：N/2次找到一般的情况。在实际中，一般情况侧重于算法的最坏情况，所以在数组中搜索数据的时间复杂度为O(N)
常见时间复杂度计算示例示例1:
void Func2(整数)
{
int count=0；
for(int k=0；k ^ 2 * N；k)
{
数数；
}
int M=10
while (M -)
{
数数；
}
printf(%d\n ，count)；
}基本运算执行2N 10次，时间复杂度为O(N)。
示例2:
void Func3(int N，int M)
{
int count=0；
for(int k=0；k M；k)
{
数数；
}
for(int k=0；k N；k)
{
数数；
}
printf(%d\n ，count)；
}基本运算执行M ^ N次，两个未知数M和N，时间复杂度为O(N ^ M)
示例3:
void Func4(int N)
{
int count=0；
for(int k=0；k 100k)
{
数数；
}
printf(%d\n ，count)；
}执行100次，无论多少常数都是1，时间复杂度为O(1)
示例4:
//计算strchr的时间复杂度？
const char * strchr ( const char * str，int character)；基本操作最好执行一次，最差执行n次。一般来说时间复杂度最差，时间复杂度为O(N)
示例5:
//计算BubbleSort的时间复杂度？
void BubbleSort(int* a，int n)
{
断言(a)；
for(size _ t end=n；结束0；-结束)
{
int exchange=0；
for(size _ t I=1；我结束；我)
{
如果(a[i-1] a[i])
{
Swap( a[i-1]，a[I])；
交换=1；
}
}
if(交换==0)
打破；
}
}时间复杂度为O (n 2)
示例6:
//计算BinarySearch的时间复杂度？
int BinarySearch(int* a，int n，int x)
{
断言(a)；
int begin=0；
int end=n-1；
while(开始结束)
{
int mid=begin((end-begin)1)；
if (a[mid] x)
begin=mid 1；
else if (a[mid] x)
end=mid
其他
返回mid
}
return-1；
}基本运算最好执行一次，最坏执行O(logN)次，时间复杂度为O(logN)。
PS: Logn表示算法分析中基数为2，对数为n。有些地方会写成lgN。(但不建议这么写)
假设我们最多搜索了x次，可以得到2 x=n，x=logn。
示例7:
//计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
如果(0==N)
返回1；
返回Fac(N-1)* N；
}递归N次，时间复杂度为O(N)。
实施例8:
//计算斐波那契递归Fib的时间复杂度？
长纤维(尺寸N)
{
if(N ^ 3)
返回1；
返回光纤(N-1)光纤(N-2)；
}
计算表明，基本运算递归2 N次(近似计算)，时间复杂度为O (2 N)。
空间复杂度空间复杂度也是一个数学表达式，是一个算法在运行过程中临时占用存储空间量的度量。
空间复杂度不是程序占了多少字节，因为没有太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则与实际复杂度基本相似，同样采用大O递进表示。
注意：堆栈空间(存储参数、局部变量、一些寄存器信息等。)已经在编译期间确定了，所以空间复杂度主要由函数在运行期间显式请求的额外空间决定。
示例1:
//计算BubbleSort的空间复杂度？
void BubbleSort(int* a，int n)
{
断言(a)；
for(size _ t end=n；结束0；-结束)
{
int exchange=0；
for(size _ t I=1；我结束；我)
{
如果(a[i-1] a[i])
{
Swap( a[i-1]，a[I])；
交换=1；
}
}
if(交换==0)
打破；
}
}使用恒定数量的额外空间，因此空间复杂度为O(1)
示例2:
//计算斐波那契的空间复杂度？
//返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{
如果(n==0)
返回NULL
long long * fib array=(long long *)malloc((n ^ 1)* sizeof(long long))；
fib array[0]=0；
fib array[1]=1；
for(int I=2；I=n；我)
{
fib array[I]=fib array[I-1]fib array[I-2]；
}
返回fibArray
}动态开辟了N个空间，空间复杂度为O(N)。
示例3:
//计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{
如果(N==0)
返回1；
返回Fac(N-1)* N；
}递归调用n次，打开n个堆栈帧，每个堆栈帧使用固定数量的空格。空间复杂度为O(N)。
摘要
算法的效率一目了然。
今天的鸡大学生能写出漂亮的代码吗？
转载请联系作者取得转载授权，否则将追究法律责任。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。