Программно найти нотацию Ландау (Big O или тета-нотацию) алгоритма?

Я привык искать нотации Ландау (Big O, Theta ...) моих алгоритмов вручную, чтобы убедиться, что они оптимизированы настолько, насколько это возможно, но когда функции становятся действительно большими и сложными, они начинают слишком много времени, чтобы сделать это вручную. это также склонно к человеческим ошибкам.

Я потратил некоторое время на Codility (упражнения по кодированию / алгоритму) и заметил, что они дадут вам нотацию Ландау для вашего представленного решения (как в использовании времени, так и памяти).

Мне было интересно, как они это делают ... Как бы вы это сделали?

Есть ли другой способ, кроме Lexical Analysis или парсинга кода?

Этот вопрос касается в основном PHP и / или JavaScript, но я открыт для любого языка и теории.

Мне было интересно, как они это делают ... Как бы вы это сделали?

Я полагаю, что они на самом деле оценивают показатели Big O ..., запуская программу для разных размеров задач, измеряя время и использование пространства и подбирая кривые к результатам.

Проблема с этим подходом состоит в том, что он может ошибиться, если функции стоимости изменяют форму, когда N становится большим; например 1000 N + N^1.5.

Есть ли другой способ, кроме Lexical Analysis или парсинга кода?

Лексический анализ и разбор не достаточны. Вы также должны сделать некоторые рассуждения о поведении алгоритма. И сделать это автоматически для ранее неизвестного алгоритма сложно.

Они не могут без анализа кода.

Приведенные ниже примеры с искусственной «инфляцией / дефляцией» сложности доказывают, что простого измерения времени выполнения программы недостаточно для надежной оценки Big-O

void lets_trick_runtime(int n) {
   if (n == 10 || n == 25 || n == 118) {
      // unfair speed-up
      do_precalculated_solution_in_constant_time(n);
      return;
   }
   if (n == 11 || n == 26 || n == 119) {
      // unfair slow-down
      do_some_fake_processing_in_n_cube_time(n);
      return;
   }
   // fair solution
   do_general_solution_in_quadratic_time(n);
}

Оценка времени выполнения для вышеупомянутого была бы возможна для того, чтобы дать ложные оценки - постоянное время для значений, nгде есть предварительно рассчитанное решение, и кубическое время для значений, где unfair slow-downначинается - вместо "справедливого" квадратичного времени.

Я думаю, что это невозможно.

Если вы запустите несколько тестов с фиксированным числом входных данных разного размера, вы можете легко вычислить полином, который будет приблизительно соответствовать времени выполнения, которое вы измерили очень хорошо. Таким образом, вы получите многочлен для каждой возможной программы, что будет означать P = NP(да!;)).

Если вы попытаетесь сделать это с помощью символических манипуляций, вы в конечном итоге в halting problem. Поскольку вы не можете решить, остановится ли ваша программа когда-либо, вы не можете решить, какую сложность во время выполнения она будет иметь.

Однако могут быть особые случаи, когда возможен более поздний метод. Но эти случаи могут быть настолько малы, что сомнительно, если усилия когда-либо будут оплачены.

Как бы я это сделал? То, как я решаю почти любую проблему, я не хочу садиться и решать . Я симулирую.

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

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

Самым большим недостатком этого метода, на мой взгляд, является то, что если ваш алгоритм действительно плохо масштабируется , то этот начальный шаг «запустите его целую кучу раз» станет уродливым. Но, честно говоря, именно так и должно быть, это само по себе должно быть индикатором того, что вы, возможно, захотите отступить и пересмотреть вещи.

Моя интуиция заключается в том, что общее решение этой проблемы невозможно; утверждение априорных фактов о времени выполнения алгоритмов без их запуска (вы ссылаетесь на лексический анализ). Тем не менее, возможен некоторый эвристический алгоритм для (возможно, большого) класса алгоритмов (поскольку мы делаем это все время), но общий алгоритм для этого будет эквивалентен решению проблемы Энтшайдунга, которая, как известно, не является возможно (ср. Черч, Тьюринг и др.). Я ~ 99,9% уверен в этом сейчас, когда я думаю об этом ...