gpt4 book ai didi

algorithm - 存储大量数字如何增加空间复杂度?

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:19:27 27 4
gpt4 key购买 nike

对于一项作业,我应该编写一个算法,允许我最多使用 n + O(log(n)) 额外的内存位(关于算法实际应该做什么的细节并不重要这里),其中 n 是输入数组的大小。

我提交了一个通过所有测试用例的算法;然而,我的评分员说我使用了超过 n + O(log(n)) 位的内存。他们的理由是,作为我算法的一部分,我将数量 (n * i) 添加到数组中的每个元素(其中 i = 1, 2, 3, ... n。i 是 a 中的索引变量环形)。他们说对于非常大的 n 值,我将使用更多内存来存储大数字。

这使我想到了以下问题:通过将 n * i 加到每个数字,我的空间复杂度是否超过 n + O(log(n)) 位是真的吗?我在算法分析方面的经验非常有限,但我个人从未见过将存储大量数字作为增加空间复杂度的理由。但是让我们说它确实增加了复杂性——我会使用超过 n + O(log(n)) 位吗?

我想提出一个挑战的论据,但我只是想在这样做之前确保我是对的。

最佳答案

b1 是每个数字在添加 (i*n) 之前的位数,b2 是之后的数字。

不等式 (1):

b2-b1 <= log(n*n) = 2log(n)

证明(一):

Lemma 1: binary number is the best coding scheme for integers in memory.

Lemma 2: The sum of 2 integers always has the result shorter than the sum of each number's sizes.

来自不等式 (1),

在极端情况下,如果b1 -> 0,则b2 = 2log(n) 所以增加的空间是2nlog(n)。总空间为 C + O(nlog(n))

免责声明:这不能证明您的问题,因为我不知道您在开始时为每个数字使用了多少位。

关于algorithm - 存储大量数字如何增加空间复杂度?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58277852/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com