问题标签 [space-complexity]

我们有一个从 1 到 100 的数字数组。缺少两个数字。使用 O(n) 时间和 O(1) 空间找到这两个数字。请注意，数组中的这些数字未排序。示例：假设有一个数组 [4, missing , 1, missing , 2] 如您所见，缺失的是 3 和 5。假设从 1 到 5 的数字数组和两个数字缺失。实际上，它是 [4, 1, 2] 没有 3 和 5。

所以，我不知道如何解决这个问题。你们有人可以帮我吗？我的编程语言是 c++。这是数组：

{24, 44, 19, 92, 1, 18, 28, 50, 88, 5, 52, 11, 76, 39, 82, 85, 65, 93, 98, 4, 72, 94, 45, 59, 48 , 46, 47, 67, 87, 99, 14, 70, 80, 25, 20, 22, 21, 41, 77, 73, 2, 13, 36, 6, 27, 81, 29, 62, 8, 35 , 32, 49, 10, 100, 90, 78, 30, 34, 51, 9, 43, 58, 26, 33, 64, 15, 17, 57, 12, 56, 61, 79, 75, 97, 84 , 42, 55, 83, 91, 86, 38, 89, 96, 74, 23, 7, 68, 60, 16, 66, 69, 53, 3, 71, 37, 63, 54, 95}

代码中的注释会增加程序的时间复杂度吗？

我有许多正在运行的应用程序，其中有在函数中注释的代码。

这些注释代码在一个函数中有 500 行，而实际代码只有 10 行。这会影响时间复杂度吗？

这些注释会使应用程序的大小变大，但是在调用带有注释代码的相应函数时会影响应用程序的效率吗？

所以我正在检查可编码性网站以进行在线代码评估。我尝试了演示示例http://codility.com/c/intro/demoRVC9C9-W8X来熟悉系统。

给出了一个由 N 个不同整数组成的零索引数组 A。该数组包含 [1..(N + 1)] 范围内的整数，这意味着恰好缺少一个元素。你的目标是找到那个缺失的元素。写一个函数：

类解决方案{公共int解决方案（int [] A）；}

给定一个零索引数组 A，返回缺失元素的值。例如，给定数组 A 使得：

A[0] = 2
A[1] = 3
A[2] = 1
A[3] = 5

该函数应返回 4，因为它是缺少的元素。假设：N是[0..100,000]范围内的整数；A 的元素都是不同的；数组 A 的每个元素都是 [1..(N + 1)] 范围内的整数。

复杂：

预期的最坏情况时间复杂度为 O(N)；

预期的最坏情况空间复杂度为 O(1)，超出输入存储（不计算输入参数所需的存储）。

可以修改输入数组的元素。

这是我在 Python 中的解决方案：

我很确定我的解决方案不会被接受，因为空间复杂度是 O(n)，其中 n 是 A 的大小。但是系统以满分接受了我的答案。我在这里错过了什么吗？

我有一个问题，我需要将一组（唯一子集）中的唯一组合与给定值相关联。例如： Let S={a, b, c, d}，所需的数据结构应执行以下操作：

键 -> 值

• 属性 1：密钥中集合的长度是固定的（在本例中固定为 2）。
• 属性 2：数据结构不包含 S 的所有可能子集。

问题 1：保存这些值的简单 Map 的存储复杂度是多少？上！）？（假设 |S| = N 并且它不是固定的）

问题 2：是否有任何有效的数据结构可以存储这些元素？（存储复杂性需要最重要的效率）

如何计算以下函数的时间和空间复杂度。我已经尝试过，但由于递归函数调用而感到困惑。

I am asked to provide the asymptotic space and time complexity of the below algorithm in appropriate terms for an initial input number of arbitrary length (as distinct from a constant 12 digits).

This algorithm is apply for a number that has 12 digits, each digit is stored in the array d[] (so we have d[1], d[2],... d[12])

I figured out the time complexity is O(n) but how do I determine the space complexity?

我在采访中被问到这个问题。这种方法的复杂性是什么？

我的作业有一个问题，要在 C++ 字符串中反转单词，就地，只有 O(1) 额外的内存。我对 O(1) 额外内存的含义感到困惑。我理解 O(1) 通常意味着什么，无论输入有多大，计算时间都是恒定的，所以我猜我应该只添加一块内存来跟踪单词的反向。有什么建议么？

给定n一个数组中的正实数，找出这个集合中是否存在三元组，使得三元组的和在 范围内(1, 2)。在线性时间和恒定空间中进行。

• 数组没有排序。
• 数字是正数
• 数字是实数

任何帮助将不胜感激。谢谢。