相关疑难解决方法(0)

有人可以帮助解释如何构建堆是O(n)复杂性？

将项插入堆中O(log n),并且插入重复n/2次(其余为叶,并且不能违反堆属性).所以,这意味着复杂性应该是O(n log n),我想.

换句话说,对于我们"堆积"的每个项目,它有可能必须针对堆的每个级别过滤一次(这是log n级别).

我错过了什么？

这个算法是mergesort,我知道这可能看起来很奇怪,但我主要关注的是计算这个算法的空间复杂度.

如果我们查看mergesort函数的递归树并尝试跟踪算法,那么堆栈大小将是log(n).但由于merge功能也有内部的mergesort,其产生的大小两个数组n/2,n/2,那么首先应该我觉得递推关系的空间复杂度,然后,我要补充的是中n/2 + n/2,这将成为O(log(n) + n).

我知道答案,但我在这个过程中感到困惑.谁能告诉我正确的程序？

这种混淆是由于合并函数,它不是递归的,而是在递归函数中调用

为什么我们说空间复杂性将O(log(n) + n)通过递归函数空间复杂度的定义,我们通常计算递归树的高度

Merge(Leftarray, Rightarray, Array) {
    nL <- length(Leftarray)
    nR <- length(Rightarray)
    i <- j <- k <- 0
    while (i < nL && j < nR) {
        if (Leftarray[i] <= Rightarray[j])
            Array[k++] <- Leftarray[i++]
        else
            Array[k++] <- Rightarray[j++]
    }
    while (i < nL) {
        Array[k++] <- Leftarray[i++]
    }
    while (j < nR) {
        Array[k++] …

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

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