这个函数的时间复杂度是0 (n)吗?

Question

我目前在一个数据结构类，这个函数会被认为是O(N)吗?我的想法是，由于while循环与for循环没有直接关联，它仍然是O(N)?如果需要更多的信息/代码来更好地上下文，我不介意编辑帖子。

感谢您的解释。

input_array = [7, 3, 4, 1, 8]
new_min_heap = []
for index in range(0, len(input_array)):
val = input_array[index]
new_min_heap.append(val)
# if new_min_heap has other values, start swappin
if len(new_min_heap) > 1:

parent_index = get_parent_index(index)
parent_val = new_min_heap[parent_index]
while val < parent_val:
new_min_heap.swap(index, parent_index)
val = parent_val
parent_index = get_parent_index(parent_index)
parent_val = new_min_heap[parent_index]

Answer 1

我假设n是输入数组的大小。

for循环的复杂度为O(n)，因为它执行了n次。内部while循环在当前数组元素和它的祖先元素之间交换值。它最多执行lg(n)次，因此复杂度为O(lg(n))。因此，总复杂度为O(n lg(n))。

Answer 2

如果有"swap value和parent_value"，你的意思是:

value, parent_value = parent_value, value

那么，while循环将是0(1)(如果while循环中没有任何其他循环)

所以整个函数将是O(n)基于数组长度

也许如果你给我们更多的背景，答案可能会改变。