小编new*_*wby的帖子

这个算法是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++] …

下面是我对队列拓扑排序算法的阅读，写在我的教科书中：

void topologicalsort(struct Graph* G){
    struct queue* Q;
    int counter;
    int v,w;
    Q=createqueue();
    counter=0;
    for(v=0;v<G->V;v++){
       if(indegree[v]==0)
          enqueue(Q,v);
       while(!isemptyqueue(Q)){
          v=dequeue(Q);
          topologicalorder[v]=++counter;
          for each w to adjacent to v
             if(--indegree[w]==0){
             enqueue(Q,w);
             }


       }
    } 
} 

对于下图，该算法失败：

如果在给定的图中最初 7 5 3 的入度为零，那么它们将被插入到队列中，但是对于与7 5 3我们相邻的任何顶点，我们都没有任何度为 1 的顶点。这意味着这if(--indegree[w]==0)将不成立，7 5 3因此有将不会在队列内进一步排队，因此该算法将不会处理更多的顶点。如果图形是 DAG，我想知道为什么算法会失败？哪种方式不正确？

我知道我们也可以使用 DFS 实现拓扑排序，但我想按原样实现以下内容：