复杂性度量问题

1.大O复杂度：嵌套加法

找出以下代码片段的 Big O 复杂度。

using System;

namespace Chapter_1

{

    class Challenge_1

    {

        static void Main(string[] args)

        {

            int n = 10;

            int sum = 0;

            float pie = 3.14F;

            for (int i = 0; i < n; i += 3)

            {

                Console.WriteLine(pie);

                for (int j = 0; j < n; j += 2)

                {

                    sum += 1;

                    Console.WriteLine(sum);

                }

            }

        }

    }

}

解决方法及说明

O(n²)

在外循环的第 11 行，int i=0;运行一次。

i<n;被执行 (n/3)+1 次，并且i+=3被执行了 n/3
次。

在内部循环中，int j=0;总共执行 (n/3) 次。j<n;执行 (n/3) * ((n/2) +1) 次，j+=2并被执行 (n/3) * (n/2) 次。

2.大O复杂度：嵌套乘法

找出以下代码片段的 Big O 复杂度。

using System;

namespace Chapter_1

{

    class Challenge_6

    {

        static void Main(string[] args)

        {

            int n = 10;

            int sum = 0;

            float pie = 3.14f;

            for (int i = 0; i < n; i++)

            {

                int j = 1;

                Console.WriteLine(pie);

                while (j < i)

                {

                    sum += 1;

                    j *= 2;

                }

            }

            Console.WriteLine(sum);

            return;

        }

    }

}

将循环变量乘以/除以常数的循环语句需要 logk n 时间，因为循环运行了很多次。在外循环中，循环变量2在每次迭代中乘以。因此，外循环运行 O(log2 n) 次。

内循环运行counter次数而不是n次数。第counter一次迭代中的值是 1，然后是 2，然后是 4，然后是 8，依此类推，直到 2^k 使得 (2^k) < n。当您counter对外循环的所有迭代的值求和时，内循环将运行：

1+2+4+8+ …+(2^k) 次。

您将使用几何级数来计算此值。为了使这个计算更简单，您必须假设 2^k = n。

(2⁰)+(2¹)+(2²)…+(2^k) = 2^(k+1)-1

(2^k)(2¹) — 1

用 n 代替 2^k 你得到：

= 2n-1

看起来内循环总共运行了 2n-1 次（考虑到外循环的所有迭代），但请记住，当 n>(2^k) 时，您假设 n = 2^k。实际上，内部循环运行的次数少于 2n-1 次，但您可以将其视为上限。

巴特西

C# 数据结构之嵌套加法、嵌套乘法

复杂性度量问题

1.大O复杂度：嵌套加法

2.大O复杂度：嵌套乘法

最新文章

热门文章