小编Dub*_*bby的帖子

在FCFS调度算法中,缺点是如果具有较高突发时间的进程P1在某些进程P2,P3 ...之前出现,具有小得多的突发时间,则平均等待时间和平均完成时间相当高.

该问题的解决方案是安排最短作业(SJF Algo).

但是如何提前计算出爆发时间？开发人员是否指定了一个公式(根据可用资源)预先计算执行作业的突发时间？

公共子串算法：

LCS(x,y) = 1+ LCS(x[0...xi-1],y[0...yj-1] if x[xi]==y[yj]
           else 0

现在动态规划解决方案很好理解。但是我无法找出递归解决方案。如果有多个子串，则上述算法似乎失败了。

例如：

x = "LABFQDB" and y = "LABDB"

应用上述算法

1+ (x=  "LABFQD" and y = "LABD")
1+ (x=  "LABFQ" and y = "LAB")
return 0 since 'Q'!='B'

返回的值将是 2，而我应该是 3？

有人可以指定递归解决方案吗？

我正在编写一个代码,涉及在C中处理维度[101] X [101]的2D数组.但是我在给定时间点使用的内存方面受到限制.

void manipulate(int grid_recv[101][101])
{
     //Something
}

void main()
{
   int grid[101][101];
   manipulate(grid);
}

所以我假设我在main()中创建了一个数组网格[101] [101],然后将其传递给另一个函数进行操作.现在函数manipulate()将整个矩阵网格复制到grid_recv中,即通过这种传递我使用两倍的内存量(即网格大小的两倍)？

当我们通过重复加倍实现动态数组时,我们只需创建一个新数组,它是当前数组大小的两倍并复制前面的元素,然后添加新的元素？正确？

所以为了计算复杂度,我们有1 + 2 + 4 + 8 + ....步数？正确？

但

 1 + 2^1 + 2^2 + .... + 2^n  =  (2^(n-1) - 1)  ~  O(2^n). 

但是有人给出了

 1 + 2 + 4 + ... + n/4 + n/2 + n  ~  O(n).

哪一个是正确的？为什么？谢谢

方法：维护两个堆栈 A 和 B。推入 A。弹出查看 B。如果 B 为空，则将 A 完全弹出并将其推入 B，然后从 B 弹出。否则简单地从 B 弹出。

问题：1）运行时间和摊销运行时间有什么区别？2）为什么这里的摊销运行时间是常数？它不会随着输入数量的增加以及我们决定从它弹出时增加吗？因为如果我们继续推动，那么 A 会填满很多，而 B 是空的。现在，如果我们决定从 B 弹出，那么我需要复制所有 A 然后弹出。

资料来源：维基百科

使用堆或其他优先级队列数据结构也可以进行流式单遍部分排序。首先，将输入的前k个元素插入结构中。然后遍历其余元素，依次将每个元素添加到结构中，并删除最大的元素。每个插入操作还需要O（log k）时间，因此总共需要O（n log k）时间。

1. 这与我们先在O（n）时间内对整个输入数组进行堆放，然后提取k次最小堆的情况有何不同？
2. 我不明白该说什么make one pass over the remaining elements, add each to the structure in turn, and remove the largest element。这与1）中描述的方法不同吗？

我有一个图，它使用 HashMap 存储它的边，如下所示：

HashMap<Integer,LinkedList<Node>> adj;

定义节点的地方；

class Node
{
   int number;
   int weight;
}

例如

• 0 : <1,55> -> <2,54> //节点0连接到边权重为55的节点1和边权重为54的节点2
• 1 : <0,43> -> <2,44> //节点1连接到边权重为43的节点0和边权重为44的节点2

我需要按重量排序的边缘列表，我不知道如何去做。我正在尝试实施 Kruskal 的 MST。

是否可以对我定义的图形进行排序？如果没有，请提出更好的存储方式。

我试图通过不同的方法找到算法的复杂性.在数学上我遇到了一个O(m + n)和另一个O(mn)方法.但是,我无法掌握或说出这一点.这不像是我看着他们并得到"啊!这就是发生了什么"的感觉!有人可以使用他们自己的例子或任何其他工具解释这个吗？