11

我对这些东西很陌生，我需要你的帮助。

我应该构建一个有效的简单算法，它返回一个大小为 n 的数组中的最大值，该数组包含重复的数字 1,2,...n。

然后我必须确定最佳运行时间、平均运行时间和最差运行时间。

所以我有两个问题：

  1. 首先，我试图理解这个简单算法需要一个有效解决方案的想法是什么。据我了解，我应该只有一个从 1 到 n 的简单循环并寻找最大值。“高效”算法是否指出如果我在数组中找到值 n 我可以停止搜索更多值，因为这是数组中的最大值？

  2. 如何使用事实确定最佳运行时间和平均运行时间，同时计算平均运行时间，这是一个均匀分布。也就是说，数组中的每个单元格都有 1/n 的机会成为最大值。

提前非常感谢！

4

4 回答 4

8

最好的情况 - 找到最大元素作为第一个 ( O(1))，最坏的情况 - 它是检查的最后一个元素 ( O(n))。

棘手的部分是平均情况。
为了找到平均情况——我们需要预期的迭代次数！

由于您可以在找到最大值后停止，因此我们可以将问题分为两部分：

  1. [0,n-1)：由于平均而言（假设每个元素的均匀独立分布） - 数字n在每个位置的概率为 1/n，因此这部分的预期迭代次数为1/n + 2*((n-1)/n)/n + 3 * ((n-1)/n)^2/n + ... + (n-1) * ((n-1)/n)^(n-2)/n 1
    上面的公式产生了一个丑陋的公式，即O(n)
  2. 如果前 n-1 个元素不包含值n: ，则将检查最后一个元素，因此您需要添加到上面的n* ((n-1)/n)^(n-1)，这O(n)也是（lim to infinity is 1/e * n）。

O(n)这在平均时间解决方案中总计。

(1)：每个元素的公式是j*((n-1)/n)^(j-1) * (1/n)因为：

  • j- 对于检查的元素数量（迭代次数）
  • ((n-1)/n)^(j-1)n-前面的元素中没有的概率
  • (1/n)- 这个数字的概率是n。
于 2012-10-31T14:18:03.723 回答
3

如果没有关于数组的先验信息（例如已排序），则没有最坏情况或最佳情况，您必须扫描所有元素以找出最大值，并且需要 O(n) 次。

此外，了解每个单元格获取最大值的概率分布通常是没有用的（除非它减少了您的搜索空间。例如，如果您知道只有恒定数量的单元格获得最大值的概率非零，那么您只需需要搜索这些单元格并且需要恒定的时间）。因此，一般来说

Best-case running time = Worst-case running time = average running time = O(n)

于 2012-11-01T03:11:48.253 回答
2

算法是这样工作的，首先你选择一个数字（在这种情况下，我选择数组的第一个数字并假装它是最大值，然后我将它与下一个数字进行比较，如果它更大，我将它作为新的最大值，直到我在数组中完成搜索），下一个代码在 C 中：

#include <stdio.h>
#define SIZE 100

typedef struct{
    int val;
    int loc;
} find;

/* Functions declaration (Prototype) */
find maxFinder( int * const a );

int main( void )
{
    int response[ SIZE ]=
       { 1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100 };

    printf( "The max number is %d located in the index %d.\n", maxFinder( response ).val, maxFinder( response ).loc );
    return 0;
}

 find maxFinder( int * const a )
 {
    /* Local Variables initialization & declaration */
    int i;
    find result;

    result.loc = 0;
    result.val = *( a + 0 );

    for( i = 1; i < SIZE; i++ ){
        if ( result.val < *( a + i ) ){
            result.loc = i;
            result.val = *( a + i );
        }
    }
    return result;
 }
于 2012-10-31T14:06:30.133 回答
1

最坏和最好的情况都很简单。平均情况更有趣。查看几何分布的维基百科页面。

于 2012-10-31T14:02:23.810 回答