В научных кругах большое значение придается разнице между алгоритмами с экспоненциальным и полиномиальным временем. Первые, как правило, трудноразрешимы более чем с десятками элементов, в то время как вторые обычно поддаются обработке до тысяч элементов. Почему? Ну, у нас есть ~ 1 миллиард операций в секунду на процессор для работы, и на практике алгоритмы экспоненциального времени обычно выполняются примерно за 2 ^ n или 3 ^ n шагов (так что n около log_3 (1B) = от 20 до log_2 (1B) = 30 обрабатывается за секунду на одном процессоре), тогда как алгоритмы с полиномиальным временем, как правило, выполняются примерно за n² или n³ (так что n около куберта (1B) = 1000 до sqrt (1B) = 30000 обрабатывается за секунду на одном процессоре). ). Конечно, там будут добавлены постоянные коэффициенты и логарифмические коэффициенты, но мы можем сбалансировать их, запустив более секунды или на большем количестве процессоров — все эти сложности, как правило, увеличивают коэффициент 10 или 100 в большинстве случаев. время.
So:
- Экспоненциальный -› десятки предметов
- Полиномиальный -› тысячи или десятки тысяч наименований
Но как насчет методов, которые работают с миллионами, миллиардами или триллионами элементов?
Для больших наборов данных мы можем сделать более ограниченный набор действий. Сортировка, группирование/подсчет, быстрое преобразование Фурье, сопоставление/уменьшение… практически все, что имеет линейную среду выполнения. Это означает O(n), O(n*log(n)) и т. д. (для тех, кто знает, что это значит: под линейностью я примерно подразумеваю O(n^(1+eps))).
Почему линейная среда выполнения особенная? Ну, экономические затраты на сбор/хранение данных растут линейно с объемом данных. Таким образом, по мере увеличения размера данных выполнение алгоритма с худшим, чем линейное, временем выполнения для всех ваших данных станет намного дороже, чем сбор и хранение данных. Другими словами: если алгоритм медленнее, чем линейный, то он никогда не сможет работать на самых больших наборах данных. Эта теория очень хорошо применима на практике: все, что медленнее, чем линейное, будет чрезмерно медленным даже на одномегапиксельном изображении, или на полном тексте книг о Гарри Поттере, или на компиляции всего кода для вашей операционной системы. И эти наборы данных даже не такие большие с экономической точки зрения — уж точно не по сравнению со всеми видео на YouTube!
Теперь самое интересное: многие вещи, связанные с вероятностью/моделированием, не являются линейными. Если кто-то передаст мне данные по целой куче разных вещей, даже простое выяснение того, какие вещи коррелируют с какими другими вещами, потребует как минимум O(n²) (а, возможно, и больше). Люди, рассуждающие о физической вселенной, часто могут обойти проблему, используя априорную информацию: насколько мы можем судить, физическая причинность локализована во времени и пространстве, поэтому в лежащей в основе причинно-следственной диаграмме имеется только линейное количество связей. Но если мы просто добавляем функции в регрессионную модель, то этот трюк не сработает.
