标签: space-complexity

我正在树上做这个基本的 dp（动态规划）问题（https://cses.fi/problemset/task/1674/）。给定公司的结构（层次结构是一棵树），任务是计算每个员工的下属人数。

这：

import sys
from functools import lru_cache  # noqa
sys.setrecursionlimit(2 * 10 ** 9)

if __name__ == "__main__":
    n: int = 200000
    boss: list[int] = list(range(1, 200001))  
    # so in my example it will be a tree with every parent having one child
    graph: list[list[int]] = [[] for _ in range(n)]

    for i in range(n-1):
        graph[boss[i] - 1].append(i+1)  # directed so neighbours of a node are only its children

    @lru_cache(None)
    def dfs(v: int) -> int:
        if …

我认为图灵机的时间复杂性和空间复杂性的辩护是相同的,我无法区分它们.

请帮我.谢谢.

当算法并不比辅助存储器的恒定量使用更多,但的确有O(log(N))递归调用(每一个走在堆栈上一些额外的空间),是算法的空间复杂度O(1)还是O(log(N))？

我正在研究时间和空间的复杂性.我以递归和迭代方式解决二叉树问题.递归使用底层堆栈,因此:

如果我想在BST中找到最小元素,那么如果我使用递归,那么我的空间复杂度就是

Worst case : O(n) if tree is left skewed OR
best case: O(1) 
average case: O(h) height of left subtree

但如果我使用迭代解决这个问题,那么空间复杂度是多少？迭代方法的空间复杂度与递归方法相同如何？我在这里没有使用任何辅助空间,我只是使用1 while循环.我在这里很困惑.

迭代方法

int minValue(struct node* node) {
  struct node* current = node;

  /* loop down to find the leftmost leaf */
  while (current->left != NULL) {
    current = current->left;
  }
  return(current->data);
}

我想要更好地理解这个想法O(n),所以我对此感到疑惑:

如果我们知道a> = b那么O(a+b)=O(a)？
我知道O(a)+O(a)=O(2a)=O(a),但是我想知道它是否真的比它小一点,我的意思是 - 如果O(a+b)=O(a).

我认为这是真的,因为a+b=O(2a),但我想知道我是不是错了......

(如果a和b是常数,PS会是真的吗？)

谢谢!

我对O(n)在太空中的含义有了高度的了解.对于具有输入n的算法而言,这意味着某些内容,此算法分配的内存中的附加存储将与n成比例增加.

因此,如果您有一个算法将数字n作为输入,并创建一个大小为2n的数组并填充它将全部为0,则时间复杂度为O(n),空间复杂度为O(n)因为您是创建一个相对于输入大小的数组(附加存储).这种理解是否正确？

其次,O(n)的空间复杂度有多糟糕？像快速排序这样的流行排序算法具有O(n)的最差情况空间复杂度,因此对于任意长数据的排序,O(n)空间复杂度是否可能具有可怕的影响？如果是这样,对于为什么或如何有任何直觉？

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

我已经研究了Eratosthenes的Sieve的工作,使用迭代生成到达给定数字的素数并且去掉所有复合数.并且算法只需要迭代到sqrt(n),其中n是我们需要找到所有素数的上限. 我们知道,与复合数的数量相比,最多n = 10 ^ 9的素数的数量非常少.因此,我们使用所有空间来通过标记它们的复合来告诉这些数字不是首要的.我的问题是我们可以修改算法只是存储素数,因为我们处理的范围非常大(因为素数的数量非常少)？我们可以直接存储素数吗？

我试图了解不同排序算法的空间复杂性.

从上面的链接http://bigocheatsheet.com/?goback=.gde_98713_member_241501229我发现冒泡排序,插入和选择排序的复杂性是O(1)
其中快速排序是O(log(n))和合并排序是O(n).

我们实际上并没有在任何算法中分配额外的内存.那么当我们使用相同的数组对它们进行排序时,为什么空间复杂性会有所不同？

试图找出铸造到字符串的时间复杂度

str([1,2,6,...,3,6])

很确定它是O(1)不知道如何验证.

编辑:关于空间复杂度,这不应该是列表大小的线性,考虑O(1)因为字符串具有最大大小.