# 确定堆创建函数的时间复杂度（Big-O）。

go评论65阅读模式

Determine Big-O of heap creation function

# 问题

``````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 &lt; n &amp;&amp; arr[left] &gt; arr[largest]) {
largest = left;
}

if(right &lt; n &amp;&amp; arr[right] &gt; arr[largest]) {
largest = right;
}

if(largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;

heapify(arr, n, largest);
}
}
``````

Thanks,

# 答案1

This is already O(log n). The value of `i` at least doubles with every recursive call, and when `i &gt;= n` it stops, and after the first call `i` is at least one, so there can be at most O(log n) recursive calls.

• 本文由 发表于 2020年10月8日 03:58:38
• 转载请务必保留本文链接：https://go.coder-hub.com/64251471.html
• algorithm
• big-o
• data-structures
• heap
• java

go 99

go 49

go 111

go 61