8

Есть функция f : неизвестный алгоритм принимающий на вход одномерный массив . Есть коллекция массивов различной длины data каждый из которых передаю в f. Необходимо написать функцию результатом которой будет строка оценивающая вычислительную сложность алгоритма в f. Функция должна различать O(n), O(n2), O(n3), O(ln(n))

Есть ли пример как программно вычисляется вычислительная сложность алгоритма? Буду благодарен любым ссылкам и материалам, желательно с простейшими примерами.

3
  • Вот вам отличная ссылка с английского so, stackoverflow.com/questions/3255/… 14 авг 2017 в 7:45
  • Если вкратце, в общем виде эта задача вам не по зубам) 14 авг 2017 в 7:48
  • 1
    Реальные алгоритмы ещё зачастую ведут себя не так предсказуемо, и эти оценки только "для худшего/среднего случая". А ещё алгоритм может быть недетерминированным (quicksort со случайным средним, например) и от вызова к вызову вести себя существенно по-разному. А ещё при увеличении объёмов обрабатываемых данных можно перестать влезать в кэш и получить внезапное и сильное замедление, причём вы не можете знать наверняка, сколько вспомогательной памяти функция использует внутри и сколько кэша вы можете себе безопасно позволить. Как вам задачка? :)
    – user181100
    14 авг 2017 в 8:07

4 ответа 4

13

Грубо - если данные достаточно разных размеров - отличающиеся на порядки - можно пытаться построить зависимость времени работы от размера и посмотреть, для какого из вариантов корреляция будет выше.

Но обычно вмешивается столько других факторов, что сказать абсолютно точно абсолютно уверенно практически нереально. Например, при T=N + 0.00000001*N^2 при том, что алгоритм - O(N2), эксперимент при реальных N даст O(N)...

12
  • Задача на вакансию джуна, неужели всё настолько сложно? 14 авг 2017 в 7:55
  • 8
    @VadimPopov бегите оттуда! Если там задают нерешаемые в общем виде задачи джунам - то уж что у сеньоров будет... 14 авг 2017 в 8:02
  • 1
    @Qwertiy Но "вычислительная сложность" и "поведение при конкретных N" - это разные концепции...
    – Harry
    24 авг 2017 в 4:32
  • 1
    @Qwertiy Ну что за беспредметный разговор...
    – Harry
    24 авг 2017 в 9:13
  • 1
    @Qwertiy Потому что точно оценить все равно невозможно. Нужно, например, иметь очень большой размах и очень большое количество данных, чтобы отличить O(n) от O(n*log n). А вообще - если это задачка экзаменационная - то важнее не что подумаете о ней вы или я, а что скажет экзаменатор :)
    – Harry
    24 авг 2017 в 13:00
9

В общем случае невозможно даже определить программно завершается ли другая программа вообще - а уж детали асимптотики определять еще труднее :-)

В качестве примера можно рассмотреть алгоритм быстрого возведения в степень. Будучи применен к кольцу вычетов или к арифметике с плавающей точкой, он дает логарифмическую асимптотику относительно показателя степени, но в длинной арифметике логарифм "теряется" и быстрое возведение в степень выполняется столь же быстро, как простое умножение - за O(N2).

Чтобы замечать такие детали, нужен сильный ИИ, способный формулировать и доказывать теоремы.

0
8

Задачи, которые сложно решить в общем случае, могут иметь простые решения, которые хорошо на практике работают во многих случаях. К примеру, Симплекс-метод имеет экспоненциальную сходимость в худшем случае, но во многих практических задачах, его время исполнения гораздо лучше (полиномиальная сходимость в среднем).

Если это допустимо в вашем случае, то вы можете померить фактические времена исполнения для доступных данных и оценить какая из моделей O(n), O(n2), O(n3) или O(log(n)) лучше описывает результаты.

К примеру, не сложно программно убедиться, какие из рассматриваемых алгоритмов являются O(1) (для используемых данных):

args key at start

Точки это измерения, а линии это соответствующие апроксимирующие полиномы.

Апроксимирующий полином вычисляется с помощью numpy.polyfit() в make-figures.py.

Вот таблица соответствия между log2(N) полиномами на графике и соответствующими функциями роста:

|------------------------------+-------------------|
| Fitting polynom              | Function          |
|------------------------------+-------------------|
| 1.00  log2(N)   +  1.25e-015 | N                 |
| 2.00  log2(N)   +  5.31e-018 | N*N               |
| 1.19  log2(N)   +      1.116 | N*log2(N)         |
| 1.37  log2(N)   +      2.232 | N*log2(N)*log2(N) |

К примеру, измерения показывают, что слияние двух отсортированных списков это O(n) операция, если используется heapq.merge() в Питоне (которая медленнее встроенного sort(), который O(n * log n) в общем случае, но так как на входе два отсортированных массива, то timsort, используемый в Питоне лучше показывает результаты):

merge_26 vs. sort_builtin for sorted random input

Конечно, измерения не всегда позволяют определить функцию роста:

time performance hamiltonian paths

См. пример кода как выполнить измерения, найти полиномы и построить графики в cdleary.py и make-figures.py

-1

Для асимптотик вида O(n^k) увеличение n вдвое ведёт к увеличению времени выполнения в 2^n раз, что довольно заметно. Так, при линейной асимптотике время будет удваиваться, при квадратичной - учетверяться, а при кубической - увеличиваться в 8 раз.

Соответственно, надо на достаточно больших n (чтобы время выполнения было ощутимым) некоторое достаточное для усреднения число раз выполнить функцию и посчитать среднее время работы. Очевидно, что при одинаковом числе повторений можено сравнивать не среднее значение, а сумму времён выполнения.

Примеры:

  • function go(n) { while (Math.random() * n | 0); } - линейная O(n) (заметно по суммарной длительности 10К вызовов при n > 2^7):

  • Сложение строк в javascript - линейная без зависимости от длины строк O(n) (заметно при n > 2^7, а где-то при n > 2^17 алгоритм меняется - такие уж они оптимизации):

  • Сложение строк в C# - квадратичная относительно числа сложений и линейная относительно длины строк O(n*n*len):

           len          !         !2       !234   !2345678
    -------------------------------------------------------
     0       1      0.000      0.000      0.000      0.000
     1       2      0.000      0.000      0.000      0.000
     2       4      0.000      0.000      0.000      0.000
     3       8      0.001      0.001      0.001      0.001
     4      16      0.002      0.001      0.001      0.002
     5      32      0.002      0.004      0.004      0.004
     6      64      0.005      0.006      0.009      0.014
     7     128      0.013      0.019      0.028      0.043
     8     256      0.042      0.057      0.087      0.148
     9     512      0.118      0.174      0.302      0.559
    10    1024      0.354      0.606      1.124      2.279
    11    2048      1.220      2.242      4.545     10.041
    12    4096      4.517      8.982     19.706     41.568
    13    8192     17.864     39.063     82.814    169.274
    14   16384     78.454    165.893    337.830    718.843
    
2
  • "О большое" так не оценить 24 авг 2017 в 5:31
  • 1
    @PavelMayorov, почему же? Дли приблизительной оценки вполне подходит.
    – Qwertiy
    24 авг 2017 в 7:46

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.