Прогнозирование производительности алгоритма, O-нотация

Вопрос:

Я применяю кластеризацию на основе k-значений в наборе текстовых полей. Вычисление выполнено следующим образом:

     1.000 records ~    4m:30s
30.000 records ~   15m:30s
100.000 records ~ 1h37m:30s

Как я могу оценить, сколько времени потребуется для завершения расчета n записей, например 500 000. Может ли кто-нибудь помочь мне с практическим примером, возможно, это будет сделано с O-Notation, я не понимаю, как это работает, жестко.

Большое спасибо.

Лучший ответ:

Обозначение “большой О” полезно, когда у вас есть теоретическое представление о поведении алгоритма. Например, вы знаете, что сравниваются O(Log(N)), чтобы найти элемент в отсортированном списке, если вы используете дихотомический поиск, вместо O(N) для линейного поиска (это в среднем, так как иногда линейный поиск может найти сразу). Кроме того, big-O – это своего рода верхняя граница, которая описывает скорость роста, но не даст вам абсолютных цифр за секунды, она более качественная, чем количественная.

В вашем случае вы больше на эмпирической стороне, и вы должны выбрать некоторую численную модель с неизвестными параметрами и найти их путем регрессии. Первым испытуемым является степенной закон: T(n)=an^b, или, выраженный в билогарифмических координатах, прямая Log(T(n)) = c. Log(n) + d Log(T(n)) = c. Log(n) + d. Поэтому желательно следить за своими точками на билогарифмическом сюжете (Excel может вам помочь).

Еще два замечания:

  • три момента действительно мало, чтобы наблюдать реальную тенденцию, и любая модель будет соответствовать одинаково хорошо;

  • что еще более важно, вы должны измерять дисперсию на время работы для разных случаев для каждого размера; потому что, если дисперсия велика, ваши прогнозы, основанные на нескольких значениях, будут просто неустойчивыми. Это требование еще сильнее, если вы хотите экстраполировать, а не интерполировать (я имею в виду делать догадки для больших значений, чем вы на самом деле пытались).

В вашем конкретном случае я наблюдаю, что три точки не выровнены хорошо и не совместимы с моделью мощности. Вы могли бы рассмотреть параболическую модель, которая будет работать нормально, но это было бы обманом: параболическая модель всегда идеально подходит для трех точек.

enter image description here

Вывод кристально чистый: вам нужно больше очков.

Оцените статью
TechArks.Ru
Добавить комментарий