我已经实现了三种不同的排序算法,现在我想确认我计算比较总数的方法是正确的。在我看来,比较的次数不应该与条件分支相关联,因为如果不满足条件,仍然会进行比较以比较值。我还使用相同的思维过程将退出循环条件的比较计数加一。
我的算法的实现如下。我是否在每种情况下都正确设置了计数器?
插入排序
int insertionSort(double* A, int arrayLength) {
int count = 1; // Initialized 1 to count for exit conditions of for loop
for (int j = 1; j < arrayLength; j++) {
count++;
double key = A[j];
int i = j - 1;
while (i > -1 && A[i] > key) {
count++;
A[i + 1] = A[i];
i = i - 1;
}
count+=2 // Plus 2 for the while loop exit condition
A[i + 1] = key;
}
return count;
}
堆排序
void heapSort(double* A, int arrayLength, int* c) {
int heapSize = 0;
buildMaxHeap(A, arrayLength, &heapSize, c);
for (int i = arrayLength - 1; i > 0; i--) {
swap(A[0], A[i]);
heapSize = heapSize - 1;
maxHeapify(A, 0, &heapSize, c);
}
}
void buildMaxHeap(double* A, int arrayLength, int* heapSize, int* c) {
*heapSize = arrayLength - 1;
*c = *c + 1; // Counts comparison of loop for exit condition
for (int i = floor((arrayLength)/ 2); i > -1; i--) {
*c = *c + 1;
maxHeapify(A, i, heapSize, c);
}
}
void maxHeapify(double* A, int i, int* heapSize, int* c) {
int l = (2 * i) + 1;
int r = (2 * i) + 2;
int largest;
if (l <= *heapSize && A[l] > A[i])
largest = l;
else largest = i;
if (r <= *heapSize && A[r] > A[largest])
largest = r;
if (largest != i) {
swap(A[i], A[largest]);
maxHeapify(A, largest, heapSize, c);
}
*c = *c + 5;
}
快速排序
void quickSort(double* A, int p, int r, int* c) {
if (p < r) {
int q = partition(A, p, r, c);
quickSort(A, p, q - 1, c);
quickSort(A, q + 1, r, c);
}
*c = *c + 1;
}
int partition(double* A, int p, int r, int* c) {
double x = A[r];
int i = p - 1;
for (int j = p; j < r; j++) {
if (A[j] <= x) {
i = i + 1;
swap(A[i], A[j]);
}
*c = *c + 2;
}
*c = *c + 1 // Adding 1 for for loop exit condition
swap(A[i + 1], A[r]);
return i + 1;
}
最佳答案
如果你看看你的插入排序
正如您已经设置的那样,count = 1 因为 for 循环的退出条件是退出。
出于同样的原因,当 while 循环取消时,内部的 count++ 将不会被执行,但进行了比较也是有道理的。 但是你计数+=2。为什么2? 这是有道理的,因为您在 while 循环中进行 2 次比较时添加了 2
(i > -1 && A[i] > key)
- i>-1
- A[i] > 键
但是随后您需要在 while 循环中将计数器增加 2,因为每次 while 都是正确的 2 次比较。
int insertionSort(double* A, int arrayLength) {
int count = 1; // Initialized 1 to count for exit conditions of for loop
for (int j = 1; j < arrayLength; j++) {
count++;
double key = A[j];
int i = j - 1;
while (i > -1 && A[i] > key) {
count++;
A[i + 1] = A[i];
i = i - 1;
}
count+2 // Plus 2 for the while loop exit condition
A[i + 1] = key;
}
return count;
}
您也可以用同样的方法检查其他算法。
仍然为了更好的方法,我建议您阅读任何有关算法分析的书籍中的一些起始章节。他们通常会解释如何估算算法的运行时间,这将帮助您了解如何更好地进行分析。
关于c++ - 检查循环条件是否应该计入比较总数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30836966/