我对这些东西很新,我需要您的帮助。
我应该构建一种有效的简单算法,该算法在数组中返回具有n个大小的最大值,其中包含数字1,2,... n带有重复。
然后,我必须确定最佳的运行时间,平均运行时间和最差的运行时间。
所以我有两个问题:
-
首先,我试图理解需要有效解决此简单算法解决方案的想法。据我所知,我应该只有一个简单的循环从1到n并寻找最大值。"有效"算法是否指出,如果我在数组中找到值n,我可以停止搜索更多值,因为这是数组中的最大值?
-
我如何使用事实确定最佳的运行时间和平均运行时间,同时计算平均运行时间,这是统一的分布。也就是说,阵列中的每个单元格都有1/n的最大值。
预先感谢!
最佳情况 - 找到最大元素作为第一个(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
1 br>上面的公式产生一个丑陋的公式,即O(n)
- 如果第一个N-1元素不包含值
n
:因此您需要添加到上述n* ((n-1)/n)^(n-1)
(即O(n)
)(LIM到Infinity是1/e * n
)。
O(n)
中的总计。
(1):每个元素的公式是j*((n-1)/n)^(j-1) * (1/n)
,因为:
-
j
-对于已检查的元素数量(迭代数) -
((n-1)/n)^(j-1)
-以前的元素中没有n
的概率 -
(1/n)
-概率此数字是n
。
如果没有关于数组的先前信息(例如,已排序),则没有最坏情况或最佳情况,并且您必须扫描所有元素才能查找最大值,并且需要O(n)次。
另外,知道每个单元格获得最大值的概率分布通常是没有用的(除非它降低了您的搜索空间。然后,您只需要搜索这些单元格,就需要持续时间)。因此,通常
最佳案例运行时间=最差的运行时间=平均运行时间= o(n)
算法是这样的,首先选择一个数字(在这种情况下,我选择数组的第一个数字并假装是最大值,然后我将其与下一个数字进行比较如果更大,我将其作为新的最大值,直到我在数组中完成搜索),下一个代码为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;
}
最坏的情况很简单。平均情况更有趣。查看Wikipedia页面以获取几何分布。
如果我们只穿越数组长度的一半怎么办?它会变成o(n/2)时间复杂性吗?
array = [6, 8, 9, 4, 100]
l = len(array)
max = 0
for i in range(l//2):
if max<array[i]:
max = array[i]
if max<array[-1-i]:
max = array[-1-i]
if l%2!=0:
if max<array[i+1]:
max = array[i+1]
print(max)
在这里,我一次从两侧遍历数组 - 是在数组中找到最大值的更快解决方案还是我们有更好的方法?