时间戳

首页 > 解决方案 > 两个问题的大 O 复杂度

time-complexity - 两个问题的大 O 复杂度

问题描述

我正在为我的一门课练习一些 Big-O 复杂性问题，这两个问题似乎最让我难过。

对于这两种情况，我需要确定最佳和最坏情况的复杂性。

第一季度

function FUNC3(int array[n], int n, int key)
    int i = 1;
    while (i < n) do {
        if (key == array[0]) then
            i = i + n^0.25;
        else
            i = i + n^0.5;
    }

我得到的最好情况是：O(n / n^0.5) 而我最坏的情况是：O(n / n^0.25)

第二季度

function FUNC4(int array[n], int n, int key)
    for (int i=1; i<n; i = i * 2) do
        for (int j=0; j<sqrt(n); j++) do {
            if(array[0] == key) then {
                int k = 1;
                while (k < n) do
                    k = k * sqrt(n);
            }
        }

对于这个，我得到了最好的情况：O(logn x sqrt(n))，最坏的情况是：O(logn xn)

虽然，我对这些答案不是很有信心，但这些看起来对吗？

标签： time-complexitybig-o

解决方案

让我们分别访问其中的每一个。这是您的第一个功能：

function FUNC3(int array[n], int n, int key)
    int i = 1;
    while (i < n) do {
        if (key == array[0]) then
            i = i + n^0.25;
        else
            i = i + n^0.5;
    }

你是正确的，最好的情况下运行时间是 Θ(n / n 0.5 )，最坏的情况是 Θ(n / n 0.25 )。通过简化指数来重写这些可能会有所帮助；第一个运行时是

Θ(n / n 0.5 ) = Θ(n 0.5 ) = Θ(√n)

第二个运行时是

Θ(n / n 0.25 ) = Θ(n 3/4 )。

现在，让我们看看第二个函数：

function FUNC4(int array[n], int n, int key)
    for (int i=1; i<n; i = i * 2) do
        for (int j=0; j<sqrt(n); j++) do {
            if(array[0] == key) then {
                int k = 1;
                while (k < n) do
                    k = k * sqrt(n);
            }
        }

为了确定运行时间，让我们使用历史悠久的格言

“当有疑问时，由内而外地工作！”

让我们从最里面的循环开始：

int k = 1;
while (k < n) do
    k = k * sqrt(n);

这个循环是偷偷摸摸的——它永远不会运行超过 3 次，因为 k 的值将是 1，然后是 √n，然后是 n。这意味着循环完成了 O(1) 的总工作。因此，我们可以将整个代码重写为

function FUNC4(int array[n], int n, int key)
    for (int i=1; i<n; i = i * 2) do
        for (int j=0; j<sqrt(n); j++) do {
            if(array[0] == key) then {
                do O(1) work;
            }
        }

由于该if语句无论是否执行都会 O(1) 工作，所以我们只剩下

function FUNC4(int array[n], int n, int key)
    for (int i=1; i<n; i = i * 2) do
        for (int j=0; j<sqrt(n); j++) do {
            do O(1) work;
        }

如果我们做 O(1) 次工作 √n 次，那么运行时间是 Θ(√n)，所以内循环变成

function FUNC4(int array[n], int n, int key)
    for (int i=1; i<n; i = i * 2) do
        do sqrt(n) work

由于内循环完成的工作与 的值无关，因此i这里完成的工作只是外循环迭代次数与一次迭代完成的工作的乘积。外循环运行 Θ(log n) 次，所以这里的工作是 Θ(√n log n)，与数组内容无关。所以这使得函数的最佳和最坏情况运行时相同，因为完成的总工作（渐近）总是相同的。

希望这可以帮助！

推荐阅读