非大O复杂度

算法复杂度的计算让我非常困惑。对于一项任务，我们给出以下功能并要求找出其复杂性。非大O复杂度

int selectkth(int a[], int k, int n) { 
    int i, j, mini, tmp; 
    for (i = 0; i < k; i++) { 
     mini = i; 
     for (j = i+1; j < n; j++) 
     if (a[j]<a[mini]) 
      mini = j; 
     tmp = a[i]; 
     a[i] = a[mini]; 
     a[mini] = tmp; 
    } 
    return a[k-1]; 
}

分配本身会询问到“寻找用于查找整数的无序阵列的第k个最小整数的函数的复杂性。”

此外我们被要求写我们的f函数以及我们的g函数。

据我所知，对于f函数，我会在函数中添加所有的赋值和操作。我在这个f函数中包含变量k或n吗？作为最佳猜测，我会说f（n）= 6n + 4（n^2），因为在循环的第一个循环中有6个循环操作，接下来是嵌套循环中的4个操作。

为了进一步理解，这个函数的大O复杂度是O（n^2）吗？我说因为有一个嵌套的for循环，这意味着每次都会遇到每个项目的最坏情况。

我很抱歉，如果我不清楚。我很困惑这是如何工作的。

来源

2014-10-09 wpaverd

你是正确的，两个嵌套的循环意味着'为O（n^2）'，海事组织试图拿出一个公式来表示的确切数目指令是一个傻瓜的差事，因为有些将成为多个CPU指令，有些将由编译器进行优化。 – IllusiveBrian 2014-10-09 02:50:51

两个嵌套循环不一定意味着'O（n^2）'。这里外环从0到k-1，这可能导致'O（kn）'而不是'O（n^2）'。（我说“可能”是因为我猜测没有形式证明。）重要的是要精确地处理变量，而不是总是将自己的思维过程简化为“两个循环=二次方= O（n^2）”。 – 2014-10-09 02:52:24

内循环执行'（n-1）+（n-2）+ ... +（n-k）'次，显然是'O（kn）'。 – 2014-10-09 04:01:07

这里去一个简单的分析：

外环做k迭代。

Inter loop正在做n-1迭代，但它的确如此k次。

因此，我们有O(k*(n-1)) = O(kn-k) 由于k可以等于n（我们可以问第n的最小整数数组中的）的表达becames O(n*n-n) = O(n^2-n) = O(n^2)。

有关大O符号符号更多的帮助，请上网：http://web.mit.edu/16.070/www/lecture/big_o.pdf

来源

2014-11-24 04:17:00

非大O复杂度

回答

相关问题