Может ли программа вычислить сложность алгоритма?

Question

Есть ли способ вычислить временную сложность алгоритма программно? Например, как я мог рассчитать сложность функции fibonacci(n)?

Answer 1

Неразрешимость halting problem говорит, что вы даже не можете сказать, завершается ли алгоритм. Я уверен, что из этого следует, что вы вообще не можете решить сложность алгоритма.

Answer 2

Подсчитайте арифметические операции, доступ к памяти и пространство памяти, используемые внутри fibbonacci(), или что бы это ни было, измерьте время его выполнения. Сделайте это с различными входами, посмотрите на возникающие тенденции, асимптотическое поведение.

Answer 3

В целом. Если алгоритм состоит из вложенных простых цепей for, например.

for (int i=a; i<b; ++i) 

то вы знаете, что это внесет вклад (b-a) шагов. Теперь, если либо b, либо a, либо оба зависят от n, тогда вы можете получить от этого сложность. Тем не менее, если у вас есть что-то более экзотическое, как

for (int i=a; i<b; i=whackyFunction(i)) 

то вам действительно нужно, чтобы понять, что whackyFunction(i) делает.

Аналогичным образом, заявления break могут испортить это, и операторы while могут быть потерянными, так как это возможно, вы даже не сможете определить, завершен ли цикл.

Answer 4

Общие меры, такие как cyclomatic complexity, полезны для того, чтобы дать вам представление о более сложных частях вашего кода, но это относительно простой механизм.

Answer 5

Хотя это невозможно сделать для всех случаев (если вы не запускаете свой собственный синтаксический анализатор кода и не смотрите на циклы и что влияет на их значения и т. Д.), Все же можно сделать это как тест черного ящика с верхней границей установить время. То есть иметь некоторую переменную, которая установлена ​​для определения того, что, как только выполнение программы пройдет на этот раз, она считается запущенной навсегда.

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

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

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

static void Main(string[] args) 
{ 
    var sw = new Stopwatch(); 

    var inputTimes = new Dictionary<int, double>(); 

    List<int> inputValues = new List<int>(); 
    for (int i = 0; i < 25; i++) 
    { 
     inputValues.Add(i); 
    } 

    var ThreadTimeout = 10000; 
    for (int i = 0; i < inputValues.Count; i++) 
    { 
     int input = inputValues[i]; 
     var WorkerThread = new Thread(t => CallMagicMethod(input)) { Name = "WorkerThread" }; 
     sw.Reset(); 
     Console.WriteLine("Input value '{0}' running...", input); 
     sw.Start(); 
     WorkerThread.Start(); 
     WorkerThread.Join(ThreadTimeout); 
     sw.Stop(); 
     if (WorkerThread.IsAlive) 
     { 
      Console.WriteLine("Input value '{0}' exceeds timeout", input); 
      WorkerThread.Abort(); 
      //break; 
      inputTimes.Add(input, double.MaxValue); 
      continue; 
     } 
     inputTimes.Add(input, sw.Elapsed.TotalMilliseconds); 
     Console.WriteLine("Input value '{0}' took {1}ms", input, sw.Elapsed.TotalMilliseconds); 

    } 

    List<int> indexes = inputTimes.Keys.OrderBy(k => k).ToList(); 

    // calculate the difference between the values: 
    for (int i = 0; i < indexes.Count - 2; i++) 
    { 
     int index0 = indexes[i]; 
     int index1 = indexes[i + 1]; 
     if (!inputTimes.ContainsKey(index1)) 
     { 
      continue; 
     } 
     int index2 = indexes[i + 2]; 
     if (!inputTimes.ContainsKey(index2)) 
     { 
      continue; 
     } 

     double[] runTimes = new double[] { inputTimes[index0], inputTimes[index1], inputTimes[index2] }; 

     if (IsRoughlyEqual(runTimes[2], runTimes[1], runTimes[0])) 
     { 
      Console.WriteLine("Execution time for input = {0} to {1} is roughly O(1)", index0, index2); 
     } 
     else if (IsRoughlyEqual(runTimes[2]/Math.Log(index2, 2), runTimes[1]/Math.Log(index1, 2), runTimes[0]/Math.Log(index0, 2))) 
     { 
      Console.WriteLine("Execution time for input = {0} to {1} is roughly O(log N)", index0, index2); 
     } 
     else if (IsRoughlyEqual(runTimes[2]/index2, runTimes[1]/index1, runTimes[0]/index0)) 
     { 
      Console.WriteLine("Execution time for input = {0} to {1} is roughly O(N)", index0, index2); 
     } 
     else if (IsRoughlyEqual(runTimes[2]/(Math.Log(index2, 2) * index2), runTimes[1]/(Math.Log(index1, 2) * index1), runTimes[0]/(Math.Log(index0, 2) * index0))) 
     { 
      Console.WriteLine("Execution time for input = {0} to {1} is roughly O(N log N)", index0, index2); 
     } 
     else 
     { 
      for (int pow = 2; pow <= 10; pow++) 
      { 
       if (IsRoughlyEqual(runTimes[2]/Math.Pow(index2, pow), runTimes[1]/Math.Pow(index1, pow), runTimes[0]/Math.Pow(index0, pow))) 
       { 
        Console.WriteLine("Execution time for input = {0} to {1} is roughly O(N^{2})", index0, index2, pow); 
        break; 
       } 
       else if (pow == 10) 
       { 
        Console.WriteLine("Execution time for input = {0} to {1} is greater than O(N^10)", index0, index2); 
       } 
      } 
     } 
    } 

    Console.WriteLine("Fin."); 
} 

private static double variance = 0.02; 

public static bool IsRoughlyEqual(double value, double lower, double upper) 
{ 
    //returns if the lower, value and upper are within a variance of the next value; 
    return IsBetween(lower, value * (1 - variance), value * (1 + variance)) && 
     IsBetween(value, upper * (1 - variance), upper * (1 + variance)); 
} 

public static bool IsBetween(double value, double lower, double upper) 
{ 
    //returns if the value is between the other 2 values +/- variance 
    lower = lower * (1 - variance); 
    upper = upper * (1 + variance); 

    return value > lower && value < upper; 
} 

public static void CallMagicMethod(int input) 
{ 
    try 
    { 
     MagicBox.MagicMethod(input); 
    } 
    catch (ThreadAbortException tae) 
    { 
    } 
    catch (Exception ex) 
    { 
     Console.WriteLine("Unexpected Exception Occured: {0}", ex.Message); 
    } 
} 

А пример вывода:

Input value '59' running... 
Input value '59' took 1711.8416ms 
Input value '14' running... 
Input value '14' took 90.9222ms 
Input value '43' running... 
Input value '43' took 902.7444ms 
Input value '22' running... 
Input value '22' took 231.5498ms 
Input value '50' running... 
Input value '50' took 1224.761ms 
Input value '27' running... 
Input value '27' took 351.3938ms 
Input value '5' running... 
Input value '5' took 9.8048ms 
Input value '28' running... 
Input value '28' took 377.8156ms 
Input value '26' running... 
Input value '26' took 325.4898ms 
Input value '46' running... 
Input value '46' took 1035.6526ms 
Execution time for input = 5 to 22 is greater than O(N^10) 
Execution time for input = 14 to 26 is roughly O(N^2) 
Execution time for input = 22 to 27 is roughly O(N^2) 
Execution time for input = 26 to 28 is roughly O(N^2) 
Execution time for input = 27 to 43 is roughly O(N^2) 
Execution time for input = 28 to 46 is roughly O(N^2) 
Execution time for input = 43 to 50 is roughly O(N^2) 
Execution time for input = 46 to 59 is roughly O(N^2) 
Fin. 

который показывает магический метод, скорее всего, O(N^2) для заданных входов +/- 2% дисперсия

, а другой результат здесь:

Input value '0' took 0.7498ms 
Input value '1' took 0.3062ms 
Input value '2' took 0.5038ms 
Input value '3' took 4.9239ms 
Input value '4' took 14.2928ms 
Input value '5' took 29.9069ms 
Input value '6' took 55.4424ms 
Input value '7' took 91.6886ms 
Input value '8' took 140.5015ms 
Input value '9' took 204.5546ms 
Input value '10' took 285.4843ms 
Input value '11' took 385.7506ms 
Input value '12' took 506.8602ms 
Input value '13' took 650.7438ms 
Input value '14' took 819.8519ms 
Input value '15' took 1015.8124ms 
Execution time for input = 0 to 2 is greater than O(N^10) 
Execution time for input = 1 to 3 is greater than O(N^10) 
Execution time for input = 2 to 4 is greater than O(N^10) 
Execution time for input = 3 to 5 is greater than O(N^10) 
Execution time for input = 4 to 6 is greater than O(N^10) 
Execution time for input = 5 to 7 is greater than O(N^10) 
Execution time for input = 6 to 8 is greater than O(N^10) 
Execution time for input = 7 to 9 is greater than O(N^10) 
Execution time for input = 8 to 10 is roughly O(N^3) 
Execution time for input = 9 to 11 is roughly O(N^3) 
Execution time for input = 10 to 12 is roughly O(N^3) 
Execution time for input = 11 to 13 is roughly O(N^3) 
Execution time for input = 12 to 14 is roughly O(N^3) 
Execution time for input = 13 to 15 is roughly O(N^3) 

Короткая ссылка указанная: O(N^3) для данного ставит +/- 2% дисперсию

Таким образом, можно программно определить сложность алгоритма, вам нужно убедиться, что вы не вводите дополнительную работу, которая заставляет ее быть длиннее, чем вы думаете (например, строительство все входные данные для функции, прежде чем вы начнете отсчет времени).

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

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