На рисунке представлена блок-схема алгоритма сортировки пузырьком. Оцените, во сколько раз увеличится время работы этого алгоритма при увеличении количества элементов в массиве сортируемых данных с 1000 до 100000, если время исполнения одной операции при этом не меняется. В ответ запишите целое число.

Question

Вопрос:

На рисунке представлена блок-схема алгоритма сортировки пузырьком. Оцените, во сколько раз увеличится время работы этого алгоритма при увеличении количества элементов в массиве сортируемых данных с 1000 до 100000, если время исполнения одной операции при этом не меняется. В ответ запишите целое число.

Фотография

Ответ ассистента

Accepted Answer

Алгоритм сортировки пузырьком имеет сложность $O(N^2)$, где $N$ — количество элементов в массиве. Это значит, что время работы алгоритма пропорционально квадрату количества элементов. Пусть $T_1$ — время работы алгоритма для $N_1 = 1000$ элементов, а $T_2$ — для $N_2 = 100 000$ элементов. Тогда: $T_1 \approx k \cdot N_1^2$ $T_2 \approx k \cdot N_2^2$ Отношение времени работы: $\frac{T_2}{T_1} = \frac{k \cdot N_2^2}{k \cdot N_1^2} = \left( \frac{N_2}{N_1} \right)^2$ Подставим значения: $\frac{100 000}{1000} = 100$ $100^2 = 10 000$ **Ответ: 10000**

Ответ ассистента

Другие решения