我现在正在学习算法,并在下面的代码中编写了该代码,该代码查找一维数组中是否存在峰。我的问题是我如何知道最佳情况或平均情况的时间复杂度?
最坏的情况是时间复杂度(如果对数组的元素进行了排序)为O(n),但是如果不对数组进行排序并且有10个元素,则代码将运行5个循环以获取结果,这是数组大小的一半,所以谁能告诉我如何用算法表示法编写此代码。
int[] arr = { 1,5,2,7,8,9,4,6,7};
int peak;
int count = 0;
for (int i = 1; i < arr.Length - 1; i++)
{
peak = -1;
if (arr[i - 1] <= arr[i] && arr[i] >= arr[i + 1])
{
peak = arr[i];
i++;
}
else if (arr[i - 1] >= arr[i] && i - 1 == 0)
{
peak = arr[i - 1];
}
else if (arr[i + 1] >= arr[i] && i + 1 == arr.Length - 1)
{
peak = arr[i + 1];
}
if (peak != -1)
listBox1.Items.Add(peak.ToString());
count++;
}
listBox1.Items.Add(count.ToString());
您仍然会这样写,O(n)
因为Big-O是最坏的情况(这里是线性时间)。在这种情况下n
,当然是数组长度。从理论上讲,循环内什么都没有超出O(1)
(我将忽略列表追加并将其称为常量。)
在注意到您对n/2
迭代的评论之后。n/2
与说相同(1/2)n
或O((1/2)n)
等同,O(n)
因为在使用Big-O进行边界时我们忽略了所有系数。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句