数据结构与算法①(第一章复杂度知识点)(大O渐进表示法)(下)

本文涉及的产品
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介: 数据结构与算法①(第一章复杂度知识点)(大O渐进表示法)

数据结构与算法①(第一章复杂度知识点)(大O渐进表示法)(上):https://developer.aliyun.com/article/1513299

实例6:计算递归版斐波那契数 Fib 的时间复杂度

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

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

答案:O(2^N)

解析:通过计算分析发现基本操作递归了2^N次,时间复杂度为O(2^N) 。

使用大O渐进法表示结果如下:


2.3空间复杂度的概念

空间复杂度的定义:空间复杂度也是一个数学表达式,是对一个算法在运行过程中临时占用存储空间大小的量度。 空间复杂度并不是程序占用了多少bytes的空间,前面在介绍算法复杂度的时候就提到了如今我们已经不再关注 "空间" ,所以关注程序占用多少byte的空间是没有太大意义的。空间复杂度算的是变量的个数! 此外,空间复杂度的计算规则基本和时间复杂度没有什么区别,同样也使用 大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(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;
}

解析:malloc 动态开辟了N个空间,空间复杂度为 O(N)


实例3:计算递归版阶乘 Fac 的空间复杂度

 
long long Fac(size_t N)
{
    if (0 == N)
        return 1;
    return Fac(N - 1) * N;
}

答案:O(N)

解析:递归调用了N次,开辟了N个栈帧,每个栈帧使用了常数个空间。空间复杂度为O(N) 。


2.4常见复杂度对比

大O对比图:

3.笔试选择题

(答案放最后)

3.1下列有关大O表示法的说法错误的是

A.大O表示法只是对程序执行时间的一个估算

B.大O表示法只保留最高阶项

C.大O表示法会保留一个系数来更准确的表示复杂度

D.大O表示法一般表示的是算法最差的运行时间

3.2分析以下函数的时间复杂度

 
void fun(int n) 
{
  int i=l;
  while(i<=n)
    i=i*2;
}

A.O(n)

B.O(n^2)

C.O(nlogn)

D.O(logn)

3.3分析以下程序的时间复杂度

 
for(int i=0;i<n;i++)
  for(int j=0;j<n;j++)
    a[i][j]=i*j;

A.O(n)

B.O(n^2)

C.O(nlogn)

D.O(logn)

3.4下面算法的时间复杂度是( )

 
int f ( unsigned int n ) 
{
    if (n == 0 || n==1) 
      return 1;
    else 
      return n * f(n-1);
  }

A.O(n)

B.O(n^2)

C.O(nlogn)

D.O(logn)

3.5给定一个整数sum,从有N个有序元素的数组中寻找元素a,b,使得a+b的结果最接近sum,最快的平均时间复杂度是( )

A.O(n)

B.O(n^2)

C.O(nlogn)

D.O(logn)

3.6分析以下函数的空间复杂度( )

 
int** fun(int n) 
{
    int** s = (int**)malloc(n * sizeof(int*));
    while (n--)
        s[n] = (int*)malloc(n * sizeof(int));
    return s;
}

A.O(n)

B.O(n^2)

C.O( 1 )

D.O(nlogn)

3.7如果一个函数的内部中只定义了一个二维数组a[3][6],请问这个函数的空间复杂度为( )

A.O(n)

B.O(n^2)

C.O( 1 )

D.O(m*n)

3.8设某算法的递推公式是T(n)=T(n-1)+n,T(0)=1,则求该算法中第n项的时间复杂度为()

A.O(n)

B.O(n^2)

C.O(nlogn)

D.O(logn)

3.9(答案)

1答案:C


解析:大O是一个渐进表示法,不会去表示精确的次数,cpu的运算速度很快,估计精确的没有意义。


2答案:D


解析: 此函数有一个循环,但是循环没有被执行n次,i每次都是2倍进行递增,所以循环只会被执行log2(n)次。


3答案:B


解析:程序有两次循环,每个循环都有n次操作,所以时间复杂度为n^2


4答案:A


解析:此函数会被递归调用n - 1次,每次操作都是一次,所以时间复杂度为n


5答案:A


解析:此题目中,数组元素有序,所以a,b两个数可以分别从开始和结尾处开始搜,


根据首尾元素的和是否大于sum,决定搜索的移动,整个数组被搜索一遍,就可以得到结果,所以最好时间复杂度为n


6答案:B


解析:此处开辟的是一个二维数组,数组有n行,每行分别有1,2,3,...n列,所以是n(n + 1)/2个元素空间,空间复杂度为n^2


7答案:C


解析:函数内部数组的大小是固定的,不论函数运行多少次,所需空间都是固定大小的,因此空间复杂度为O(1)


8答案: A


解析:


T(n)


=T(n-1)+n


=T(n-2)+(n-1)+n


=T(n-3)+(n-2)+(n-1)+n


...


=T(0)+1+2+...+(n-2)+(n-1)+n


=1+1+2+...+(n-2)+(n-1)+n


从递推公式中可以看到,第n项的值需要从n-1开始递归,一直递归到0次结束,共递归了n-1次


所以时间复杂度为n

本篇完。(附下篇对应OJ链接)

下一篇更新这一篇的相关力扣OJ。

目录
相关文章
|
4月前
|
存储
数据结构—顺序表(如果想知道顺序表的全部基础知识点,那么只看这一篇就足够了!)
数据结构—顺序表(如果想知道顺序表的全部基础知识点,那么只看这一篇就足够了!)
|
13天前
|
算法 搜索推荐 开发者
别再让复杂度拖你后腿!Python 算法设计与分析实战,教你如何精准评估与优化!
在 Python 编程中,算法的性能至关重要。本文将带您深入了解算法复杂度的概念,包括时间复杂度和空间复杂度。通过具体的例子,如冒泡排序算法 (`O(n^2)` 时间复杂度,`O(1)` 空间复杂度),我们将展示如何评估算法的性能。同时,我们还会介绍如何优化算法,例如使用 Python 的内置函数 `max` 来提高查找最大值的效率,或利用哈希表将查找时间从 `O(n)` 降至 `O(1)`。此外,还将介绍使用 `timeit` 模块等工具来评估算法性能的方法。通过不断实践,您将能更高效地优化 Python 程序。
30 4
|
11天前
|
算法 程序员 Python
程序员必看!Python复杂度分析全攻略,让你的算法设计既快又省内存!
在编程领域,Python以简洁的语法和强大的库支持成为众多程序员的首选语言。然而,性能优化仍是挑战。本文将带你深入了解Python算法的复杂度分析,从时间与空间复杂度入手,分享四大最佳实践:选择合适算法、优化实现、利用Python特性减少空间消耗及定期评估调整,助你写出高效且节省内存的代码,轻松应对各种编程挑战。
23 1
|
2月前
|
机器学习/深度学习 存储 算法
【初阶数据结构篇】时间(空间)复杂度
复杂度是计算机科学中的一个基础概念,它帮助我们理解和评估算法的效率,对于算法设计和优化至关重要。
【初阶数据结构篇】时间(空间)复杂度
|
2月前
|
算法
【初阶数据结构】复杂度算法题篇
该方法基于如下的事实:当我们将数组的元素向右移动 k 次后,尾部 kmodn 个元素会移动至数组头部,其余元素向后移动 kmodn 个位置。
|
3月前
|
算法 搜索推荐 开发者
别再让复杂度拖你后腿!Python 算法设计与分析实战,教你如何精准评估与优化!
【7月更文挑战第23天】在Python编程中,掌握算法复杂度—时间与空间消耗,是提升程序效能的关键。算法如冒泡排序($O(n^2)$时间/$O(1)$空间),或使用Python内置函数找最大值($O(n)$时间),需精确诊断与优化。数据结构如哈希表可将查找从$O(n)$降至$O(1)$。运用`timeit`模块评估性能,深入理解数据结构和算法,使Python代码更高效。持续实践与学习,精通复杂度管理。
54 9
|
3月前
|
机器学习/深度学习 存储 算法
【数据结构】算法的复杂度
算法的时间复杂度和空间复杂度
54 1
【数据结构】算法的复杂度
|
2月前
|
存储 算法
【数据结构】复杂度(长期维护)
【数据结构】复杂度(长期维护)
|
4月前
|
存储 Java API
Java数据结构之ArrayList(如果想知道Java中有关ArrayList的知识点,那么只看这一篇就足够了!)
Java数据结构之ArrayList(如果想知道Java中有关ArrayList的知识点,那么只看这一篇就足够了!)
Java数据结构之ArrayList(如果想知道Java中有关ArrayList的知识点,那么只看这一篇就足够了!)
下一篇
无影云桌面