数据结构和算法学习记录——空间复杂度的计算(冒泡排序、阶乘递归、斐波那契数列递归、常见复杂度对比、栈帧、栈溢出)

简介: 数据结构和算法学习记录——空间复杂度的计算(冒泡排序、阶乘递归、斐波那契数列递归、常见复杂度对比、栈帧、栈溢出)

一、简单介绍

空间复杂度也是一个数学函数表达式,是对一个算法在运行过程中 临时额外占用存储空间大小的量度。 空间复杂度不是不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是额外创建的变量的个数。 空间复杂度的计算规则基本跟时间复杂度类似,也使用   大O渐进表示法  

注:函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时候显示申请的额外空间来确定。

下面用实例来加深一下理解

二、冒泡排序的空间复杂度

2-1

//计算BullleSort的空间复杂度?
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;
    }
}

看上面所写的冒泡排序,我们要算额外创建的变量的个数。那么就是函数内部创建的变量(即不包括int*a,int n)


其中在第一个for循环中创建了第一个变量size_t end,第二个变量int exchange,嵌套的for循环里创建了第三个变量size_t i,共计三个变量。循环一轮结束,局部变量销毁,新一轮的循环创建的变量占用的是用一块空间,是重复的。


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


所以冒泡排序的额外变量个数为3个,即常数个。


故而冒泡排序的空间复杂度为:O(1)。

三、阶乘递归的空间复杂度

3-1

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

算递归的空间复杂度,主要要看递归的深度。一次调用Fac()时额外创建的变量是常数个,空间复杂度记为O(1)。

递归调用了N次,开辟了N个栈帧,每个栈帧使用了常数个空间,最终这个阶乘递归的空间复杂度为:O(N)。

栈帧

栈的概念: 在数据结构中, 栈是限定仅在表尾进行插入或删除操作的线性表。栈是一种数据结构,它按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据。

栈帧的概念:

每一次函数的调用,都会在调用栈(call stack)上维护一个独立的栈帧(stack frame).每个独立的栈帧一般包括:

1. 函数的返回地址和参数

2. 临时变量: 包括函数的非静态局部变量以及编译器自动生成的其他临时变量

3. 函数调用的上下文

四、斐波那契数列递归的空间复杂度

4-1

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

一开始可能会误以为答案是 ,但一想下来,如果空间复杂度为 的话,只要给出一个N = 50就会发生栈溢出了。显然是不合理的,在前面看冒泡排序的空间复杂度的时候讲过,空间是不累积的,使用过的空间依旧能再次被使用。

或者这么想,我们把Fib(N)到Fib(0)全都调用过一遍了,其余在调用他们的时候都是在Fib(N)到Fib(0)中重复的,而重复使用的是同一块空间。所以Fib()的空间复杂度为O(N)。

栈溢出

栈溢出指的是程序向栈中某个变量中写入的字节数超过了这个变量本身所申请的字节数,因而导致与其相邻的栈中的变量的值被改变。

五、常见复杂度对比(转载)

O(1) — 常数复杂度

O(log n) — 对数复杂度

O(n) — 线性复杂度

O(n log n) — 对数线性复杂度

O(nᵏ) — 多项式复杂度

O(kⁿ) — 指数复杂度

O(n!) — 阶乘复杂度

下图描绘了各种复杂度的算法中,当输入规模增长时,操作数量(运行时间)的变化趋势。

你可以看到,随着输入规模的增长,红色阴影区域中算法的运行时间急剧增长。另一方面,在黄色和绿色阴影区域中的算法,当输入规模增长时,运行时间在变化不是很大,因此它们更高效,处理大量数据时更游刃有余。


最后需要指明的一点,大 O 表示法通常用于描述当输入规模变得非常大时,算法呈现的「显著趋势」。因此,大的显著趋势会盖过一些小的细枝末节的趋势。例如,我们实际测算得到时间复杂度为 O(n²+ n) 的算法会简化为 O(n²),原因是随着 n 变得非常大时, n² 这一项的显著性远远盖过了 n 这一项的显著性。


目录
相关文章
|
3天前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
142 77
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
38 7
|
1月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
44 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
46 9
|
2月前
|
算法
【算法】栈
栈相关算法题,供参考,附有链接地址及板书
|
2月前
|
缓存 算法 搜索推荐
Java中的算法优化与复杂度分析
在Java开发中,理解和优化算法的时间复杂度和空间复杂度是提升程序性能的关键。通过合理选择数据结构、避免重复计算、应用分治法等策略,可以显著提高算法效率。在实际开发中,应该根据具体需求和场景,选择合适的优化方法,从而编写出高效、可靠的代码。
50 6
|
3月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
99 5
|
3月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
72 0
|
3月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
54 1

热门文章

最新文章