Вердикт по замерам
Коллега прогнал чужую программу на входах разного размера и прислал таблицу: размер входа n и время работы. Исходников нет, а ответить нужно сегодня: как растёт её время? Выберите одну из восьми моделей:
1, log n, n, n log n, n^1.585, n^2, n^3, 2^n.
Замеры шумные, но не слишком. Для верной модели f найдётся такое число c > 0, что каждое время отличается от c·f(n) не больше чем на 10 %: 0,9·c·f(n) ≤ t ≤ 1,1·c·f(n). А для любой другой модели g ни при каком c не выйдет, чтобы все времена сразу отличались от c·g(n) меньше чем на 20 %. Поэтому ответ всегда один.
Во втором примере — настоящий замер: Python умножает два случайных числа по n бит, лучший из девяти запусков.
Вход
В первой строке число замеров m (3 ≤ m ≤ 40). Дальше m строк: целое n (2 ≤ n ≤ 109) и время t — положительное число не больше 1012, в обычной или экспоненциальной записи (0.00617, 4.07876e-05). Размеры идут по возрастанию и не повторяются.
Выход
Модель ровно так, как она записана выше, например n log n.
Примеры
Пример 1
10 1000 0.197877 2000 0.44526 4000 0.962032 8000 2.33301 16000 4.5603 32000 10.1556 64000 20.8713 128000 43.8851 256000 100.572 512000 209.795
n log n
Пример 2
8 4096 0.00617 8192 0.01972 16384 0.05788 32768 0.17655 65536 0.52948 131072 1.65769 262144 5.11409 524288 14.7766
n^1.585
Ограничения
- Время · Python
- 2000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 12 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Наклон на логарифмических осях — первое, что приходит в голову. Посчитайте его для первого примера. Какую модель он подсказывает и почему это не ответ?
2Подсказка 2
Если модель верна, то t/f(n) почти не меняется: это и есть c с шумом. Как по набору чисел t/f(n) узнать, найдётся ли одно c, от которого все они отличаются не больше чем на 20 %?
3Идея
Поделим время на каждую модель и посмотрим на разброс: отношение наибольшего частного t/f(n) к наименьшему. Все частные помещаются в коридор c·(1 ± r) при каком-нибудь c ровно тогда, когда разброс не больше (1 + r)/(1 − r). Для верной модели разброс не больше 1,1/0,9 ≈ 1,22, для любой другой — не меньше 1,2/0,8 = 1,5. Значит, ответ — модель с наименьшим разбросом.
4Разбор
Почему коридор и разброс — одно и то же. Пусть частные лежат между qmin и qmax. Коридор [c(1 − r), c(1 + r)] их накрывает, если c(1 − r) ≤ qmin и c(1 + r) ≥ qmax, то есть qmax/(1 + r) ≤ c ≤ qmin/(1 − r). Такое c есть, если левая граница не больше правой: qmax/qmin ≤ (1 + r)/(1 − r). Сам множитель c искать не нужно.
Считать удобнее в логарифмах: ln t − ln f(n), а разброс — разность наибольшего и наименьшего. Так деление становится вычитанием, а 2n при n = 109 не переполняет числа: ln 2n = n ln 2. Основание логарифма в моделях log n и n log n не важно: оно меняет все частные в одно и то же число раз, и разброс остаётся прежним.
В первом примере наклон по всем точкам — около 1,1, и округление даёт «n». Но частные t/n растут от первого замера к последнему вдвое, а t/(n log n) стоят на месте с точностью до шума. Локальный наклон n log n равен 1 + 1/ln n, и на таких n он как раз около 1,1: логарифмический множитель прячется в десятых долях наклона. Во втором примере наклон держится около 1,6, и это не шум, а log2 3 ≈ 1,585: Python умножает большие числа алгоритмом Карацубы. Подробно о проверке отношением, о близнецах n log n и n1,1 и о том, где замеры врут, — в статье «Сложность по замерам».
Здесь частные берутся по всем замерам, потому что шум ограничен условием. На настоящих замерах так делать не стоит: на малых n время портят постоянные расходы — запуск, вызов, выделение памяти, — и проверку отношением ведут по верхней половине размеров.
4+Решение
5Сложность
O(8·m): по одному проходу по замерам на каждую модель.
6Типичные ошибки
- Округлить наклон.
n log nпревращается вn, аlog n— в1: первый пример, четвёртый и восьмой тесты. - Наклон по двум последним точкам. Один отрезок — это два замера, и шум обоих целиком попадает в ответ: при 10 % на замер наклон отрезка между n и 2n может уйти на ±0,3.
- Считать 2n в числах. При n до 109 это переполнение, а частное t/2n обращается в ноль. Нужны логарифмы.
- Подбирать c по первому замеру. Если взять c = t1/f(n1) и проверять отклонение остальных, шум первого замера ложится на все: верная модель может «не пройти» 10 %. Смотрите на разброс частных — он от выбора c не зависит.