当前位置： 文江博客话题详情

程序可以计算算法的复杂度吗？

发布于 2024-12-26 05:08:30 字数 69 浏览 0 评论 0原文

有没有办法以编程方式计算算法的时间复杂度？例如，如何计算 fibonacci(n) 函数的复杂度？

原文

Is there any way to compute the time complexity of an algorithm programatically? For example, how could I calculate the complexity of a fibonacci(n) function?

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（5）

梦巷 2025-01-02 05:08:30

停止问题的不确定性表明您甚至无法判断算法是否终止。我非常确定，您通常无法解决算法的复杂性。

The undecidability of the halting problem says that you can't even tell if an algorithm terminates. I'm pretty sure from this it follows that you can't generally solve the complexity of an algorithm.

回复 原文
情话墙 2025-01-02 05:08:30

虽然不可能对所有情况都这样做（除非您运行自己的代码解析器并只查看循环以及对其值的影响等），但仍然可以使用上限时间集进行黑盒测试。也就是说，设置一些变量来确定一旦程序的执行经过这个时间，它就被认为是永远运行的。

从这里你的代码看起来与此类似（快速而肮脏的代码抱歉它有点冗长，并且对于我没有检查过的更大的权力，数学可能会关闭）。

可以通过使用输入值的集合数组而不是随机生成一些值来改进它，并且通过检查更广泛的值，您应该能够检查任何输入与任何其他两个输入，并确定方法持续时间的所有模式。

我确信有比这里显示的更好（即更准确）的方法来计算一组给定数字之间的 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.

这表明对于给定输入 +/- 2% 方差，魔术方法可能是 O(N^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 证明编码算法的速度与正如您所说，它可以是（忽略对常量的改进）。

While it's impossible to do for all cases (unless you run your own code parser and just look at loops and what impacts on their values and such), it is still possible to do as a black box test with an upper bound time set. That is to say, have some variable that is set to determine that once a program's execution passes this time it's considered to be running forever.

From this your code would look similar to this (quick and dirty code sorry it's a little verbose and the math might be off for larger powers I haven't checked).

It can be improved upon by using a set array of input values rather than randomly generating some, and also by checking a wider range of values, you should be able to check any input versus any other two inputs and determine all the patterns of method duration.

I'm sure there are much better (namely more accurate) ways to calculate the O between a set of given numbers than shown here (which neglects to relate the run time between elements too much).

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);
    }
}

And an example output:

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.

Which shows the magic method is likely O(N^2) for the given inputs +/- 2% variance

and another result here:

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)

Which shows the magic method is likely O(N^3) for the given inputs +/- 2% variance

So It is possible to programatically determine the complexity of an algorithm, you need to make sure that you do not introduce some additional work which causes it to be longer than you think (such as building all the input for the function before you start timing it).

Further to this you also need to remember that this is going to take a significant time to try a large series of possible values and return how long it took, a more realistic test is to just call your function at a large realistic upper bound value and determine if it's response time is sufficient for your usage.

You likely would only need to do this if you are performing black box testing without source code (and can't use something like Reflector to view the source), or if you have to prove to a PHB that the coded algorithms are as fast as it can be (ignoring improvements to constants), as you claim it is.

回复 原文
盗琴音 2025-01-02 05:08:30

不是一般情况下。例如，如果算法由嵌套的简单 for 循环组成，

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

那么您就知道这将贡献 (ba) 步骤。现在，如果 b 或 a 或两者都依赖于 n，那么您可以从中获得复杂性。但是，如果您有一些更奇特的东西，那么

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

您确实需要了解 whackyFunction(i) 的作用。

类似地，break 语句可能会搞砸，而 while 语句可能会失败，因为您甚至可能无法判断循环是否终止。

Not in general. If the algorithm consists of nested simple for loops, e.g.

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

then you know this will contribute (b-a) steps. Now, if either b or a or both depends on n, then you can get a complexity from that. However, if you have something more exotic, like

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

then you really need to understand what whackyFunction(i) does.

Similarly, break statements may screw this up, and while statements may be a lost cause since it's possible you wouldn't even be able to tell if the loop terminated.

回复 原文
听不够的曲调 2025-01-02 05:08:30

计算 fibbonacci() 或其他任何内容中使用的算术运算、内存访问和内存空间，测量其执行时间。使用不同的输入来执行此操作，查看新兴趋势和渐近行为。

Count arithmetic operations, memory accesses and memory space used inside fibbonacci() or whatever it is, measure its execution time. Do this with different inputs, see the emerging trends, the asymptotic behavior.

回复 原文
浮世清欢 2025-01-02 05:08:30

像圈复杂度这样的一般度量有助于让您了解代码中更复杂的部分，但这是一个相对简单的机制。

General measures like cyclomatic complexity are useful in giving you an idea of the more complex portions of your code, but it is a relatively simple mechanism.

回复 原文
~没有更多了~

关于作者

西瑶

暂无简介

文章
评论
26 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

忆悲凉

文章 0 评论 0

hgfg1645

文章 0 评论 0

qq_qLPLYi

文章 0 评论 0

戏舞

文章 0 评论 0

殊姿

文章 0 评论 0

﹂绝世的画

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文