你会把这种算法的时间复杂度称为什么？

Question

我使用的是C#语法,但这个问题并不仅限于C#.

例1

public static long Do(long n)
{
    var sqrt = (long)Math.Sqrt(n);

    for(long i = 0; i < sqrt; i++)
        // do something

    return result;
}

这仍然是线性时间,即使在最坏的情况下,我们只做平方根时间的操作n,这只是一小部分n？

例2

您将如何对下面算法的时间复杂度进行分类？

public static long Do(long n)
{
    while (n > 1)
    {
        n = (long)Math.Sqrt(n);

        // do something
    }

    return result;
}

在最坏的情况下,这会被称为在对数时间内完成的操作,即使我们再一次不仅仅是将迭代次数减半,而是将它们减少一个数量级,而不仅仅是一半.

Answer 1

第一个代码片段仅包含一个循环以及该循环之外的恒定数量的操作。如果这个循环迭代了k很多次，而每次迭代都需要t时间，那么它的复杂度就是O(kt)。这里，k等于sqrt(n)，这意味着如果循环不包含非常量时间操作（例如，如果它不包含嵌套循环或循环函数等），则该片段的时间复杂度等于O(sqrt(n))也写为O(\xe2\x88\x9an)。

\n\n

事实上，这里有一个循环并不意味着任何复杂性。例如，以下代码具有两个嵌套循环，具有线性复杂度：

\n\n

int j = 0;\nfor (int i = 0; i < n; ++i)\n{\n    for (; j < n; ++j)\n    {\n        // A loop with constant-time operations and eventual breaks\n    }\n}\n

\n\n

在这个例子中，i从0到n，因此我们花O(n)时间增加i。类似地，j从0到n，我们进行变量O(n)增量j以及O(n)内部循环体的迭代。由于这段代码中没有其他操作，因此总复杂度为O(n) + O(n) + O(n) = O(n)。

\n\n

为了处理第二个例子，我以递归方式重写它：

\n\n

int Do(int n)\n{\n    // Do something with constant-time compexity\n    return n > 1 ? Do(sqrt(n)) : result;\n}\n

\n\n

我们将此示例的时间复杂度称为T(n)。我们可以看到，T(n) = 1 + T(sqrt(n))该函数第一部分的计算时间（恒定）被视为时间单位。求解这个递归方程给出我们T(n) = log log n（这里的对数是二进制的）。的确，1 + log log(sqrt(n)) = 1 + log ((log n) / 2) = 1 + log log n - 1 = log log n。对于渐近表达式，使用哪个对数底并不重要，因为log_a x = log_a b * log_b x = O(log_b x)，这就是通常省略对数底的原因。

\n\n

因此，复杂性是：O(\xe2\x88\x9an)和O(log log n)。

\n\n

UP：为了非严格地估计你的复杂性，可以使用 Excel 或任何其他软件工具进行计算。您只需构建一个不同值的操作数表n，并尝试猜测复杂性规则。例如，对于问题中的代码片段#2：

\n\n

\n\nN 操作日志 n 日志 日志 n \n1 1 0 - \n2 2 1 0\n4 3 2 1\n16 4 4 2\n256 5 8 3\n65536 6 16 4\n\n

\n\n

正确答案通常从表格中显而易见

\n