space-complexity 相关问题

算法的空间复杂度量化算法运行所占的内存量，作为问题输入大小的函数。算法的空间复杂度通常使用大O表示法表示，其抑制乘法常数和低阶项。

为什么向字母键控哈希映射添加值的程序的空间复杂度不是线性的？

想象一个程序，它采用长度为 p 的字符串作为参数，并通过使用仅使用英文字母表的 26 个字母作为 k 的哈希映射，对每个出现的字母加 1 来计数......

data-structures hashmap counting space-complexity

回答 1 投票 0

展平任意深度的嵌套列表的空间和时间复杂度

给定一个包含任意嵌套级别的嵌套列表的 python 列表，目标是返回一个完全扁平化的列表，即对于样本输入 [1, [2], [[[3]]], 1]，输出应该是...

python time-complexity nested-lists space-complexity

回答 1 投票 0

二叉树上广度优先搜索的空间复杂度是多少？

这是我的Java解决方案，用于通过广度优先搜索逐级打印二叉树（它有效！！）公共无效 printByLevel() { System.out.print("按级别排列的元素："); if(总体根！=

algorithm tree time-complexity breadth-first-search space-complexity

回答 1 投票 0

遍历数组元素的空间复杂度[关闭]

我有一个C++代码片段。 int sumOfArray( int * arr, int size ) { 整数分辨率=0；对于 ( int i=0 ; i 我有一个 C++ 代码片段。 int sumOfArray( int * arr, int size ) { int res=0; for ( int i=0 ; i<size; i++ ) res= res+arr[i]; return res; } 我对该代码片段的空间复杂度感到困惑。你能指导我它的复杂度是恒定的还是线性的？程序中使用的空间通常是衡量除输入之外还读取/写入多少空间的指标。在您的情况下，int * arr是您程序的输入（您可以使其成为const，而无需以任何其他方式修改您的程序）。 int sumOfArray( int const*const arr, int size ) { int res=0; for ( int i=0 ; i<size; i++ ) res= res+arr[i]; return res; } 由于您没有使用 arr 作为暂存空间，因此您用作暂存和输出空间的唯一数据是 res。 res的大小是sizeof(int)，它不是输入参数的函数。这意味着你的时间复杂度为 O(1)。然而，这实际上并非如此，因为 arr 的元素总和的最大值随着 arr 中元素的数量而增长。您编写的程序有一个错误 - 如果 arr 的元素加起来超过 int 的最大值，您的程序将无法回答问题。要解决此问题，您需要将大小字段设置为 BigInt，并将返回值设置为 BigInt。 BigInt 以其大小的对数增长。因此，“正确”的无错误版本的总和实际上会使用 O(log(n)) 空间。然而，人们经常忽略由整数大小限制引起的 log(n) 因子，并假装整数可以容纳无限量的数据。有趣的是，这个假设实际上使所有程序都占用 O(1) 空间，因为您可以细分无限的整数以在其中存储无限的数据。 ;)

c++ space-complexity

回答 1 投票 0

数组元素之和函数的空间复杂度

我有一个C++代码片段。 int sumOfArray( int * arr, int size ) { 整数分辨率=0；对于 ( int i=0 ; i 我有一个 C++ 代码片段。 int sumOfArray( int * arr, int size ) { int res=0; for ( int i=0 ; i<size; i++ ) res= res+arr[i]; return res; } 我对该代码片段的空间复杂度感到困惑。你能指导我它的复杂度是恒定的还是线性的？程序中使用的空间通常是衡量除输入之外还读取/写入多少空间的指标。在您的情况下，int * arr是您程序的输入（您可以使其成为const，而无需以任何其他方式修改您的程序）。 int sumOfArray( int const*const arr, int size ) { int res=0; for ( int i=0 ; i<size; i++ ) res= res+arr[i]; return res; } 由于您没有使用 arr 作为暂存空间，因此您用作暂存和输出空间的唯一数据是 res。 res的大小是sizeof(int)，它不是输入参数的函数。这意味着你的时间复杂度为 O(1)。然而，这实际上并非如此，因为 arr 的元素总和的最大值随着 arr 中元素的数量而增长。您编写的程序有一个错误 - 如果 arr 的元素加起来超过 int 的最大值，您的程序将无法回答问题。要解决此问题，您需要将大小字段设置为 BigInt，并将返回值设置为 BigInt。 BigInt 以其大小的对数增长。因此，总和的“正确”无错误版本实际上会使用 O(log(n)) 空间。然而，人们经常忽略由整数大小限制引起的 log(n) 因子，并假装整数可以容纳无限量的数据。有趣的是，这个假设实际上使所有程序都占用 O(1) 空间，因为您可以细分无限的整数以在其中存储无限的数据。 ;)

c++ space-complexity

回答 1 投票 0

trie 相当于 C++ 中的 std::map<std::string, int> 吗？

trie 的通常实现相当于标准::地图在 C++ 中？所谓等价，我的意思是：它们是否具有相同的空间复杂度，以及它们各自的操作...

c++ time-complexity trie space-complexity

回答 2 投票 0

二叉搜索树上递归调用的空间复杂度

我正在做一个测验，这是提出的问题之一：您已经在平衡二叉搜索树上实现了一些递归算法，其中部分需要在左侧递归，然后重新...

recursion space-complexity

回答 1 投票 0

使用哈希图对字谜进行分组的空间复杂度

我正在解决一道leetcode问题。问：给定一个字符串数组 strs，将所有字谜词组合在一起子列表。您可以按任何顺序返回输出。注意：strs[i]由小写英文组成