Сумма троек

1.

Пример: сумма троек

Сумма троек. Возьмем N целых чисел. Сколько
сумм трех чисел равно нулю?

2.

Сумма троек: метод грубой силы

3.

4.

5.

Эмпирический анализ

Запуск программы с различными входными
данными и измерение времени выполнения

6.

Анализ данных

Шкала с линейным масштабом

7.

Свойства быстрого поиска

Логарифмическая шкала

Регрессия. Провести прямую линию через точки: aNb

Гипотеза. Время выполнения 1,006 * 10-10 * N2,999 секунд

8.

Предсказание и проверка

Гипотеза. Время выполнения 1,006 * 10-10 * N2,999 секунд

Предсказание.


51,0 секунда для N = 8000

408,1 секунда для N = 16000
Наблюдение.

9.

Удвоение гипотезы


Запустить программу с удвоенным размером входных
данных
Гипотеза. Время выполнения aNb, где b = log2 (ratio)

10.

Удвоение гипотезы

Вопрос: Как оценить а (если мы знаем b)?

Ответ: Запустить программу (на большом наборе данных N) и найти a.

Гипотеза. Время выполнения 0,998 * 10-10 * N3

11.

Экспериментальная алгоритмика