这是一个使用两个递归调用对数组进行排序的算法。我试图粗略地计算其时间复杂度,但不确定。我知道两个for循环需要n次,但是递归调用怎么办,我如何计算它们呢?任何人都可以用简单的数学方法帮助计算。
MySort (a[1..n] , n) {
If (n <= 2) {
If (first element > second) && (n = 2) then do
{ Interchange a[1] & a[2]; }
End if
}
Else
{ Assign value to min and max by very first element of array.
for (i : = 1 to n) do
{ If (a[i] > max) then
max = a[i];
Else if (a[i] < min) then
min = a[i]; //Get max and min element from the array. }
End for
Calculate MID value of the MAXIMUM & MINIMUM element found.
For i : = 1 to n do
{
If(a[i] < mid) then { Increment Count1 by 1; and P[Count1]=a[i] }
Else if (a[i] > mid) then { Increment Count2 by 1; and Q[Count2]=a[i] }
//Divide the major array to sub-arrays;
//Count1 and Count2 are counters to make check on the size of sub-arrays generated.
}
End for
MySort (P, Count1);
MSort (Q, Count2); }
End if}
有两个循环,后跟两个递归调用。理想情况下,每次调用都会将输入大小减半,从而得到n/2的值。这给出了一个递归关系:
T(n) = n + n + T(n/2) + T(n/2)
T(n) = 2n + 2T(n/2)
这与主定理页面上给出的表格的最后一行相匹配:
T(n) = O(nlogn)
如果输入输入在每次调用时不均匀划分,则需要n^2时间,因为每次调用时大小可能只能减少1:
T(n) = 2n + T(n-1) + T(1)
T(n) = nT(1) + 2n + 2(n-1) + 2(n-2) + ...
T(n) = O(n^2)
这个问题是为了修改过去的试卷,如果我走上了正确的道路,我需要一些建议。 求出下面一段代码的时间复杂度,表示给定整数n的操作次数: 所以我认为外循环是,第一个内环是,第二个内环是。我只是想知道我是否有一个大致的想法,以及如何从这里继续前进。
我遇到了这个代码。它只扫描数组元素一次。但我对有两个嵌套的while循环将复杂性增加到O(n^2)感到困惑。代码如下: 我正在学习算法,所以如果我哪里出了问题,请纠正我。非常感谢。
我在理解算法的时间复杂性方面有问题。 让我们举第一个例子,用这个算法在二叉搜索树中进行搜索: 那么,如何计算这个时间复杂度呢? null
我在计算一个方法的时间复杂度: D总是小于或等于P,但我的怀疑是在后四个。我的时间复杂度是O(2p^3),但我读过2可以像O(p^3)一样去掉。这些是正确的吗?
所以我在理解为什么递归DFS和迭代DFS的时间复杂度相同时遇到了一些问题,也许有人能给我一个简单的解释? 提前谢了。
我有一个算法可以检查是否可以解决游戏行。游戏行是一个正整数数组,其中最后一个元素为 0。游戏标记从索引 0 开始,沿着数组移动它所在的整数指示的步数。 例如,[1,1,0]返回true,而[1,2,0]返回false。标记也可以向左或向右移动以解决游戏。也就是说,[3,3,2,2,0]是可解的。 我尝试了一些游戏行示例,并计算了最坏情况下的时间复杂度: 其他情况下给我的数字,我找不到与输入大小的关