gpt4 book ai didi

algorithm - 给定算法的最坏情况运行时间是多少

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:33:49 25 4
gpt4 key购买 nike

有人在我的学术论文中问过我这个问题。请让我知道答案?

 arrayFind(x, A)
i =0 ;
while( i < n ) {
if(x==A[i])
return i;
else
i = i+1;
}
return –1;

假设我们有一个算法,find2D( ),在二维空间中找到元素 xn x n 数组 A。算法 find2D( ) 遍历 A 的行并对每一行调用算法 arrayFind() 直到 x 已找到或已搜索 A 的所有行。

这个算法最坏情况下的运行时间是多少

一个。如果每一行的元素都排序了?
b.如果每行中的元素未排序?

最佳答案

根据给定的信息,排序/不排序对最坏的情况没有影响。在这两种情况下,最坏的情况是要找到最新行中的最新元素。在那种情况下,运行时间将为 O(n^2),其中 n 具有您用 n x n 指出的含义。它是 n x n,因为您必须遍历 n 行,然后在每一行中进行 n 比较。

如果您使用二进制搜索,排序示例的最坏情况运行时间为 O(n log n),最坏情况是,搜索的元素位于最后一行的中间。

关于algorithm - 给定算法的最坏情况运行时间是多少,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21646264/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com