英文:
Determine Big-O of heap creation function
问题
以下是翻译好的部分：
这个 heapify 方法的时间复杂度的大O表示是多少？我原以为是 O(log n)，但好像不太对？如何使它变成 O(log n)？
假设我们有以下代码：
int arr[] = {1, 3, 5, 2, 7, 9, 4, 6};
int n = arr.length;
int i = 0; // 起始位置
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
英文:
What is the Big-O notation of this heapify method? I was expecting O(log n) but it does not add up? How do I make it O(log n)?
Assuming we have this:
int arr[] = {1, 3, 5, 2, 7, 9, 4, 6};
int n = arr.length;
int i = 0; // Start position
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if(left < n && arr[left] > arr[largest]) {
largest = left;
}
if(right < n && arr[right] > arr[largest]) {
largest = right;
}
if(largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
Thanks,
答案1
得分: 1
这已经是 O(log n)。i 的值在每次递归调用时至少加倍，当 i >= n 时停止，在第一次调用后，i 至少为 1，因此递归调用最多可以有 O(log n) 次。
英文:
This is already O(log n). The value of i at least doubles with every recursive call, and when i >= n it stops, and after the first call i is at least one, so there can be at most O(log n) recursive calls.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论