简单的“阵中的最大值”和复杂的计算(Simple “maximum value in array”

我很新的这东西，我需要你的帮助。

我应该建立一个有效的简单的算法，该算法在具有n的尺寸的阵列，其包含1,2，... n，其中重复返回最大值。

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

所以，我有两个问题：

首先我想了解什么是需要为这个简单的算法有效的解决方案的想法。据我了解，我应该只需要一个简单的循环，从1到n，寻找最大值。是“有效”的算法指出，如果我发现数组中的值n我可以停止搜索更多的价值，因为这是在数组中的最大价值？
如何确定使用的事实，在计算平均运行时间，这是一个均匀分布的最佳运行时间和平均运行时间。即，阵列中的每个单元具有的1 / n机会成为最大值。

非常感谢提前！

Answer 1:

最好的情况下-找出最大元素作为第一（ O(1)最坏的情况下-这是检查（最后一个元素O(n)

最棘手的部分是平均情况。
要查找平均情况下-我们需要的预计迭代次数！

既然你也可以在你停止寻找最大的，我们可以分割问题分为两个部分：

[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 ¹
上述式产生难看的公式是O(n)
最后一个元素将被检查，如果第一n-1个元素不包含价值n ：所以你需要添加到上述n* ((n-1)/n)^(n-1)这是O(n)以及（LIM到无穷是1/e * n ）。

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

（1）：对于每个元件的公式是j*((n-1)/n)^(j-1) * (1/n)因为：

j -用于检查元件的数目（迭代次数）
((n-1)/n)^(j-1) -概率没有n在前面的元件
(1/n) -概率这个数目n 。

Answer 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;
 }