程序员经验分享-hwhale

空间复杂度的定义

2023-12-12

通过时间复杂度，我们将算法的运行时间理解为输入大小（表示内存中的实例所需的位数）的函数。那么对于这个观察，我们如何定义空间复杂度呢？这显然与实例的大小无关......


空间复杂度可以通过多种方式定义，但通常的定义如下。我们假设输入存储在只读存储器中的某个位置，有一个专用的只写存储器用于存储操作的结果，并且有一些通用的“临时空间”存储器用于进行辅助计算。通常，空间复杂度是存储输出和所有临时空间所需的空间量。例如，二分查找的空间复杂度为 O(1)，因为只需要 O(1) 存储空间来存储输入和输出（假设数组索引适合机器字）。

有时，输入和输出空间被组合成单个存储单元并且输入可以被修改。例如，在该模型中，对于合并所需的辅助存储空间，堆排序的空间复杂度为 O(1)，而归并排序的空间复杂度为 O(n)。

希望这可以帮助！

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

complexitytheory

timecomplexity

spacecomplexity

空间复杂度的定义 的相关文章

  • 层序遍历的时间复杂度

    二叉树层次顺序遍历的时间复杂度是多少 是 O n 还是 O log n void levelorder Node n queue lt Node gt q q enqueue n while q empty Node node q fron

  • 通过维护顺序来聚合重复记录，并且还包括重复记录

    我正在尝试解决一个有趣的问题 很容易只做一个 groupBy 来进行聚合 如求和 计数等 但这个问题略有不同 让我解释 这是我的元组列表 val repeatSmokers List String String String String

  • 这个函数是 O(N+M) 还是 O(N*M)？

    def solution M A result 0 M maxCount 0 setAll 0 for i in range 0 len A if A i M 1 setAll maxCount maxCount 0 result 0 M

  • 稳定的比较排序，时间复杂度为 O(n * log(n))，空间复杂度为 O(1)

    在经历的同时维基百科的排序算法列表 https secure wikimedia org wikipedia en wiki Sorting algorithm Comparison of algorithms我注意到没有稳定的比较排序 h

  • 在 JavaScript 中使用 filter() 查找两个未排序数组的交集的 Big O

    我刚刚开始学习 Big O 表示法 我试图理解不同函数的 Big O 看看哪个更好 我正在努力计算时间和空间复杂度对于以下代码 function findCommonElem arr1 arr2 let result arr1 filter

  • 计算所有结构不同的二叉树的数量的时间复杂度是多少？

    使用此处介绍的方法 http cslibrary stanford edu 110 BinaryTrees html java http cslibrary stanford edu 110 BinaryTrees html java 12

  • 在线性时间内打印出不相交集数据结构中的节点

    我正在尝试在 Cormen 等人的 算法简介 中进行此练习 该练习与分离集数据结构有关 假设我们要添加操作PRINT SET x 给定 一个节点x并打印所有成员x已设置 按任何顺序 展示如何 我们可以只向不相交集中的每个节点添加一个属性 森

  • 集合运算的复杂性

    这就是我正在做的 字符串一 某个字符串 字符串二 某个字符串 我想知道字符串中的所有字符one and two它们应该按第一串中的顺序排列 我编写了一个 Java 程序 它通过使用 Collections 对两个集合执行设置操作 我想知道执

  • array[::-1] 的时间复杂度和空间复杂度是多少

    当在Python中反转列表时 我通常使用数组 1 进行反转 并且我知道更常见的方法可能是从列表的两侧进行交换 但我不确定这两种解决方案之间的区别 例如时间复杂度和空间复杂度 这两种方法的代码如下 def reverse array arra

  • 创建二叉树的时间复杂度

    我正在尝试从提供的源创建一棵树 要添加到树中的 2 个节点 以及应添加这 2 个新闻节点的节点 为了找到该节点在树中的位置 我使用了中序遍历 该遍历的时间复杂度为 O n 因此 如果要在树中添加 n 个节点 则创建整个树的时间复杂度为 O

  • 寻找最接近的斐波那契数列

    我正在尝试解决一个更大的问题 并且我认为该程序的重 要部分花费在低效的计算上 我需要计算给定数字 N 的区间 P Q 其中 P 是 到 N 的最小斐波那契数 目前 我正在使用地图来记录斐波那契数的值 查询通常涉及搜索最多 N 的所有斐波那契

  • 计算数组中向量之间的最大距离

    假设我们有一个包含 n 个向量的数组 我们想要计算这些向量之间的最大欧氏距离 最简单 天真的 的方法是迭代数组 并为每个向量计算其与所有后续向量的距离 然后找到最大值 然而 这个算法会增长 n 1 相对于数组的大小 对于这个问题还有其他更有

  • 这段代码的复杂度是多少？ （大O）这是线性的吗？

    for int i 0 i

  • 找出数组中重复的元素

    有一个大小为 n 的数组 数组中包含的元素在 1 到 n 1 之间 每个元素出现一次 只有一个元素出现多次 我们需要找到这个元素 尽管这是一个非常常见的常见问题解答 但我仍然没有找到正确的答案 大多数建议是我应该将数组中的所有元素相加 然后

  • 查找集合列表中不相交集合对的数量

    问题陈述如下 给定一个包含 n 个集合的列表 每个集合包含 k 个整数 找到不相交集合对的数量 假设集合的可能元素为正 且上界为 c gt n 并且假设 k 我试图想出一种有效的算法来比 O kn 2 更快地解决这个问题 这是简单解决方案的

  • 在不存储整个数组的情况下单遍查找第 K 大数

    我想到的算法是 保持大小为 K 的最大堆 插入每个元素 如果堆已满 则丢弃较小的值 最后 第K个max是MaxHeap中较小的一个 这将给我 O NlogK 有更好的算法吗 我无法进行快速选择 因为数组无法存储在内存中 根据您的内存限制 您

  • gsub的时间复杂度

    一根长绳子s仅包含0 and 1 这段 Ruby 代码计算了有多少个1有 s gsub 1 count Big O 表示法的时间复杂度是多少 有没有一个工具可以进行计算 据我所知 没有一个通用工具可以计算任意代码的 Big O 表示法 这将

  • 旅行商问题中 NP 难问题和 NP 完全问题的混淆

    旅行商优化 TSP OPT 是一个NP难题 旅行商搜索 TSP 是NP完全问题 然而 TSP OPT 可以简化为 TSP 因为如果 TSP 可以在多项式时间内求解 那么 TSP OPT 1 也可以 我认为要将 A 简化为 B B 必须与 A

  • 带 If 的嵌套 For 循环的时间复杂度

    void f int n for int i 1 i lt n i if i int sqrt n 0 for int k 0 k lt pow i 3 k do something 我的思考过程 执行if语句的次数 sum i 1 to

  • hashmap包含键的复杂度

    我写了一个方法来查找列表中的重复项 它工作正常 但我担心使用 containsKey 的复杂性 当我们使用 containsKey 时 我们必须为每个键计算一个哈希函数 然后将每个键与我们的搜索项进行比较 对吗 那么复杂度不是 O n 吗

随机推荐

  • Microsoft Office OneNote C++ API？

    我正在考虑通过 C 编程修改 Microsoft Office OneNote 内容 具体在使用快速归档对话框界面 但是那里提供的所有示例都是针对C 的 我想知道C 的API是否可用 如果有的话我可以从哪里开始学习它们 我只是想使用该对话框

  • Angular 5测试组件静态方法

    我正在测试的 Component 类上有一个静态方法 我的问题是如何在我的规范测试文件中访问该方法 到目前为止 我可以通过以下方式访问组件实例 let fixture TestBed createComponent MyComponent

  • 如何执行递归搜索？

    我有一个任务类 它可以有相同类型的子任务 public class Task public DateTime Start get set public DateTime Finish get set public List

  • 我对套接字的 fwrite 不会刷新，直到套接字关闭。如何改变？

    我对套接字的 fwrite 不会刷新 直到套接字关闭 如何改变 我希望它在每次写入后刷新 我试过了 1 冲洗 2 刷新 3 ob implicit flush 真 这些都不起作用 我仍然必须退出 php 让我的套接字接收数据 包括一些示例代

  • Rails：如何使用范围在数组数组中查找元素

    我有一个数组数组 例如 2 3 3 1 6 1 每个子数组的第一个元素是用户 ID 第二个元素是用户为活动预订的座位数 我想让每个用户通过在数组中查找他的 ID 来查看他的预订 假设我有两个模型 用户和事件 在用户控制器中 我想使用类似的范

  • 唯一标识调试器中的引用类型

    我有 C 背景 如果这是非 C 的思维方式 我很抱歉 但我只需要知道 在 C 中 如果我有两个指针 并且我想知道它们是否指向同一对象 我可以查看内存 监视窗口并查看它们的值 看看它们是否指向相同的内存空间 在 C 中 我还没有找到类似的东西

  • Silverlight 中的对象深复制

    我试图创建对象的副本银光5其中 IFormatters 和 IcCloanble 等接口不支持 我的对象是这样的 注意这些对象是在反序列化xml时获得的 我尝试像这样复制 XmlRoot ElementName component publ

  • 如何更改每个选项卡的颜色？

    我有一个表单 上面有四个选项卡 我希望每个选项卡具有不同的颜色 我在互联网上找到的唯一内容是如何更改所选选项卡的颜色 而其余选项卡保持原始颜色 我还没有找到任何东西可以为每个选项卡赋予自己的颜色 我目前拥有的代码是 Private Sub

  • 通过谷歌脚本更改表单调色板

    我需要帮助 我正在使用 Google 应用程序脚本来创建 Google 表单 如何更改表单的颜色 调色板 我试图在这里找到https developers google com apps script reference forms 但什么

  • 如何使用 Xamarin Forms 创建具有垂直粘性标题和水平粘性第一列的表格？

    在显示表格数据时 我认为在某些情况下 具有始终可见的标题行和始终可见的第一列确实可以提高表格的可读性和整体可用性 特别是当表格中有大量数据时 当表格必须支持水平和垂直滚动时 就会出现问题 在查看过去比赛的得分时 可以从 NBA 应用程序中找

  • 整数线性编程 Java：有多种开源和商业工具可用。使用哪一个？

    我需要为我的应用程序使用整数线性编程 API 工具 虽然我的应用程序是用 Java 编写的 但我不介意从 Java 调用 EXE 工具 使用文件 MPS 等 提供输入 我的搜索分析如下 有多种开源和商业工具可用于解决 ILP 以下问题 我发

  • 如何在Python中获取函数的实际参数名称？

    例如 def func a how to get the name x x 1 func x 如果我使用inspect模块我可以获得堆栈帧对象 import inspect def func a print inspect stack ou

  • WPF - 如何以编程方式备份​​/恢复 LocalDB - ClickOnce

    我有一个使用 EF 和 LocalDB 作为数据库的应用程序 由 ClickOnce 发布 这是我第一次使用 LocalDB 我不知道如何向我的应用程序添加一个功能来以编程方式备份 恢复数据库 我的 ClickOnce 安装的应用程序路径

  • 使用 UITextPosition，从 textInRange 获取前一个字符

    我一直在寻找 但不知道如何做到这一点 假设我有一个这样的字符串 NSString string foo foo 我想做的是区分文本视图中的两个 foo 听起来很有趣哈哈 当我单击一个时 我想知道它前面是哪个 或 我是这样理解这个词的 UIT

  • PBKDF2 Excel UDF 以及如何连接 INT(i)

    最近 我一直在深入研究密码学 并在 Excel 中使用哈希和加密函数 我可能会在我正在从事的项目中使用这些函数 我使用简单的哈希函数 例如 Function Hash ByVal plainText As String Dim utf8En

  • 如何从另一个observeEvent访问数据帧？

    一个例子 UI R library shiny shinyUI fluidPage titlePanel Example sidebarLayout sidebarPanel radioButtons orderdata Sort by c

  • 如何在 Ruby 1.9 中调试 require

    根据the Tin Man的意见 我提出一个新问题 原来的问题在这里 Rubygem 如何需要所有宝石 我用来调试的原始代码 require debugger debugger require thor 这是一个两难的境地 使用默认值进行调

  • 在 Microsoft R Open 上安装软件包失败

    我在 R 上安装软件包时从未遇到过任何问题 但在 Microsoft R Open 上安装软件包时总是遇到问题 例如 我尝试安装 tidyverse 我收到了很多错误 如下所示 gt Warning in system cmd error

  • java.lang.IncompleteClassChangeError：类“org.apache.http.message.BasicHeader”未实现接口“org.apache.http.NameValuePair”

    我有一个问题Released APK java lang IncompatibleClassChangeError安装并打开发布的 APK 时出现错误 但我的调试 APK 工作正常 我看到了很多链接和 stackoverflow 问题 但没

  • 空间复杂度的定义

    通过时间复杂度 我们将算法的运行时间理解为输入大小 表示内存中的实例所需的位数 的函数 那么对于这个观察 我们如何定义空间复杂度呢 这显然与实例的大小无关 空间复杂度可以通过多种方式定义 但通常的定义如下 我们假设输入存储在只读存储器中的某

热门标签