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

Question

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

Answer 1

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

Answer 2

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

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

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

Я уверен, что есть гораздо лучшие (а именно более точные) способы вычисления 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, чтозакодированные алгоритмы настолько быстры, насколько это возможно (игнорируя улучшения констант), как вы утверждаете, что это так.

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

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

Answer 5

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