所以基本上，我试图了解应该如何计算双调排序的时间复杂度，以及使用成本和时间决定最佳和最坏情况的情况，然后对值进行加法和乘法。
举个例子:我先尝试计算插入排序的复杂度。
void sort(int A[]){ Cost Time
for (int i = 1; i < A.length; i++) c1 n
{
int key = A[i]; c2 n-1
int j = i-1; c3 n-1
while (j >= 0 && A[j] > key){ c4 Σ (j=2 to n) of t_j
A[j+1] = A[j]; c5 Σ (j=2 to n) of (t_j-1)
j = j-1; c6 Σ (j=2 to n) of (t_j-1)
}
A[j+1] = key; c7 n-1
}
}
t_j - 是执行“while”循环的次数。
T(n) = c1*n + c2(n-1) + c3(n-1) + c4(Σ (j=2 to n) of t_j) +
+c5(Σ (j=2 to n) of (t_j-1)) + c6(Σ (j=2 to n) of (t_j-1)) + c7(n-1)
所以在最好的情况下 t_j = 1，那么: T(n) = an + b; (a, b - 常量)
在最坏情况下 t_j = j，则:T(n) = an^2 + bn + c;
所以 - O(n) - 最好的情况？ O(n^2) - 更坏的情况？
但是我真的不明白双调排序方法等操作的成本和时间应该是多少，例如这样的代码:
public class BitonicSorter implements Sorter
{
private int[] a;
private final static boolean ASCENDING=true, DESCENDING=false;
public void sort(int[] a)
{
this.a=a;
bitonicSort(0, a.length, ASCENDING);
}
private void bitonicSort(int lo, int n, boolean dir)
{
if (n>1)
{
int m=n/2;
bitonicSort(lo, m, ASCENDING);
bitonicSort(lo+m, m, DESCENDING);
bitonicMerge(lo, n, dir);
}
}
private void bitonicMerge(int lo, int n, boolean dir)
{
if (n>1)
{
int m=n/2;
for (int i=lo; i<lo+m; i++)
compare(i, i+m, dir);
bitonicMerge(lo, m, dir);
bitonicMerge(lo+m, m, dir);
}
}
private void compare(int i, int j, boolean dir)
{
if (dir==(a[i]>a[j]))
exchange(i, j);
}
private void exchange(int i, int j)
{
int t=a[i];
a[i]=a[j];
a[j]=t;
}
}
也许有人曾经尝试过计算这种排序算法的复杂性，并且可以举一个成本和时间的例子？或引用了解应归因于哪些成本和时间？
P.S 我是新手，没有正确理解应该如何“计算”，所以请随时提出建议。欣赏。
最佳答案
要分析递归过程，您需要编写并解决递归问题。在这里，设 S(n) 是对 n 元素进行排序的比较次数，M(n) 是要合并的比较次数 n 个元素。
S(1) = 0
for n > 1, S(n) = 2 S(n/2) + M(n)
M(1) = 0
for n > 1, M(n) = 2 M(n/2) + n/2
我们可以使用 Master Theorem 的情况 2|解决这些问题。
M(n) = Theta(n log n)
S(n) = 2 S(n/2) + Theta(n log n) = Theta(n (log n)^2)
关于algorithm - 双调排序(计算复杂度)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/49223372/