На рисунке представлена блок-схема алгоритма сортировки пузырьком. При N = 100 000 время выполнения алгоритма составляет 0,8 с. Оцените время выполнения алгоритма (в секундах) при N = 500 000, если время выполнения одной операции постоянно. В ответ запишите целое число.

Решение:

Алгоритм сортировки пузырьком имеет сложность \( O(N^2) \), где \( N \) — количество элементов массива.

Время выполнения алгоритма пропорционально квадрату количества элементов:

\( T \propto N^2 \)

Дано:

• \( N_1 = 100 000 \)
• \( T_1 = 0.8 \) с
• \( N_2 = 500 000 \)

Найдём \( T_2 \).

Отношение времён выполнения будет равно отношению квадратов количества элементов:

\( \frac{T_2}{T_1} = \frac{N_2^2}{N_1^2} \)

\( T_2 = T_1 \cdot \left(\frac{N_2}{N_1}\right)^2 \)

\( T_2 = 0.8 \text{ с} \cdot \left(\frac{500 000}{100 000}\right)^2 \)

\( T_2 = 0.8 \text{ с} \cdot (5)^2 \)

\( T_2 = 0.8 \text{ с} \cdot 25 \)

\( T_2 = 20 \text{ с} \)

Ответ: 20