标签: space-complexity

假设对于各种输入字符串，算法生成具有相同数量的 0 和 1 的二进制字符串。两个不同输入字符串的输出可能相同也可能不同。我们能谈谈算法的空间复杂度吗？

在浏览了一些SO 帖子后，我发现埃拉托色尼筛法是生成素数的最佳且最快的方法。

我想生成两个数字之间的素数，例如a和b。

AFAIK，在 Sieve 方法中，空间复杂度为O(b)。

PS：我写的是Big-O而不是Theta，因为我不知道空间要求是否可以减少。

我们可以降低埃拉托斯特尼筛法的空间复杂度吗？

如果我的想法是错误的，请纠正我。我认为 BigO(V + E) = BigO(V^2)。

以下是我的想法：
完整图中的边 = n*(n-1)/2。

从 E 和 V 切换到 n，因为这样对我来说更容易思考。

E = n*(n-1)/2
V = n

BigO(V + E) => BigO(n + n*(n-1)/2) => BigO(n^2)

将 n 切换回 V。

=> BigO(v^2)

我错过了什么吗？为什么使用 BigO(V + E)？为什么不使用BigO(V^2)？

split/strip/open（内置python函数）的时间/空间复杂度是多少？

有谁知道我可以在哪里查看这些函数的时间/空间复杂度？

谁能告诉我这个 Dijkstra 算法中优先级队列的空间复杂度。请注意，此处一个顶点可以多次添加到队列中。然而，由于访问集的原因，它不会被处理多次。这就是为什么我想知道队列的最大大小可以达到的原因。

def shortestReach(n, edges, start,target):

    adjList = collections.defaultdict(list)

    for parent, child, cost in edges:
        parent -= 1
        child -= 1
        adjList[parent].append((child, cost))
        adjList[child].append((parent, cost))

    priorityQueue = queue.PriorityQueue()
    priorityQueue.put((0, start))
    visited = set()
    while priorityQueue.qsize() > 0:
        costPar, parent = priorityQueue.get()

        if parent == target:
            return costPar

        if parent not in visited:
            for adj in adjList[parent]:
                child, cost = adj
                priorityQueue.put((cost + costPar, child))

        visited.add(parent)

这是一个python问题。答案应该是 O(n) 时间复杂度并且不使用额外的内存。作为输入，我得到一个应该归类为回文或不归类的字符串（回文是一个单词或短语，可以从左到右和从右到左阅读相同的单词或短语，fe“级别”）。在输入中可以有标点符号和单词之间的间隙。例如“我。做了，，，我是吗？？？？” 主要目标是确定输入是否为回文。

当我试图解决这个问题时，我遇到了几个挑战。当我尝试删除非字母数字时

for element in string:
    if ord(element) not in range(97, 122):
        string.remove(element)
    if ord(element) == 32:
        string.remove(element)

我使用 O(n^2) 复杂度，因为对于字符串中的每个元素，我都使用 remove 函数，它本身具有 O(n) 复杂度，其中 n 是列表的长度。我需要帮助通过消除 O(n) 复杂度的非字母字符来优化部件

此外，当我们去掉空格作为标点符号时，我知道如何检查一个单词是否是回文，但我的方法使用了额外的内存。

乍一看，合并排序的空间复杂度为 O(n) 是有道理的，因为为了对未排序的数组进行排序，我要拆分并创建子数组，但所有子数组的大小总和将为 n。

问题：我主要关心的是递归期间 mergeSort() 函数的内存分配。我有一个主堆栈，对 mergeSort() （递归）的每个函数调用都将被推送到堆栈上。现在，每个递归调用的 mergeSort() 函数都将拥有自己的堆栈。因此，假设我们对 mergeSort() 进行了 5 次递归调用，那么主堆栈将包含 5 个函数调用，其中每个函数调用都有自己的函数堆栈。现在，每个函数堆栈都有自己的局部变量，例如函数创建的左子数组和右子数组。因此，5 个函数堆栈中的每一个在内存中都应该有 5 个不同的子数组。那么空间不应该随着递归调用的增长而增长吗？

我读到O(n log n)大于O(n)，我需要知道为什么会这样？

例如取n为 1，求解O(n log n)为O(1 log 1)= O(0)。在同一手上O(n)会是O(1)？

这实际上是矛盾的 O(n log n) > O(n)

最近，我正在处理一个大文本文件（~10GB）并尝试替换Python中的一些字符。

我尝试了这两个版本：

f = open('myFile.txt', 'r')
filedata = f.read()
filedata = filedata.replace(',', ' ').replace('-', ' ').replace('_', ' ')

f = open('myFile.txt', 'r')
filedata = f.read()
filedata = filedata.replace(',', ' ')
filedata = filedata.replace('-', ' ')
filedata = filedata.replace('_', ' ')

当我尝试第一个时，该进程在替换方法期间被终止。然而，当我使用第二个时，该进程并没有被杀死。（截屏。）

>>> f = open('myFile.txt', 'r')
... filedata = f.read()
... filedata = filedata.replace(',', ' ').replace('-', ' ').replace('_', ' ')
Killed

>>> f = open('myFile.txt', 'r')
... filedata = f.read()
... filedata = filedata.replace(',', ' ')
... filedata = …

大O记法的正式定义是，如果我们有一个函数f(n)（时间和算法的空间）和其他功能g(x)，并有常数c，并no使得c*g(n) > f(x)所有n > no的话f(n) = O(g(n))。但是使用这个定义以及不断增长的二次函数总是会在某个时候超过线性函数的事实，所有O(n)函数都是真的O(n²)吗？或者更好地说，是n = O(n²)？