Есть код с пирамидальной сортировкой, и мне нужно показать что в зависимости от количества элементов в массиве скорость пропорционально изменяется в О(nlogn) раз. Можно ли сказать, что время при n=6 деленное на время при n=3 будет примерно равно 6log6/3log3 и какая в таком случае приемлемая погрешность? Потому что я пытался так делать и значение деленного времени у меня было 2.25, при том если делить логарифмы то там будет значение 3.26. Может кто-то предложит более показательное решение.
import time
# Define the customHeapSort function
def customHeapSort(arr):
# Define a helper function for the down-heap operation
def customDownHeap(arr, k, n):
# Store the value of the element at index k
new_element = arr[k]
# Loop until the index k reaches the last level of the heap (floor division)
while k <= n // 2:
# Calculate the index of the left child
child = 2 * k
# Compare the left and right child, if the right child exists and is greater, choose it
if child < n and arr[child] < arr[child + 1]:
child += 1
# If the new element is greater than or equal to the child, break the loop
if new_element >= arr[child]:
break
# Move the child up and update its index
arr[k] = arr[child]
k = child
# Place the new element in its correct position
arr[k] = new_element
# Get the size of the array
size = len(arr)
# Build the heap by performing down-heap operations on non-leaf nodes
for i in range(size // 2 - 1, -1, -1):
customDownHeap(arr, i, size - 1)
# Extract elements from the heap one by one and reconstruct the heap
for i in range(size - 1, 0, -1):
# Swap the root (maximum element) with the last element
temp = arr[i]
arr[i] = arr[0]
arr[0] = temp
# Perform down-heap operation on the root to restore the heap property
customDownHeap(arr, 0, i - 1)
# Return the sorted array
return arr
# Example usage
arr = [12, 1, 5, -10, 45, 2]
# Measure the execution time of the algorithm
start_time = time.time()
sorted_arr = customHeapSort(arr)
end_time = time.time()
# Calculate the time taken
execution_time = end_time - start_time
# Print the sorted array and the execution time
print("Sorted array is:", sorted_arr)
execution_time = "{:.10f}".format(execution_time)
print("Execution time:", execution_time, "seconds")
Простой
