算法的时间复杂度

程序是

我现在正在学习算法,并在下面的代码中编写了该代码,该代码查找一维数组中是否存在峰。我的问题是我如何知道最佳情况或平均情况的时间复杂度?

最坏的情况是时间复杂度(如果对数组的元素进行了排序)为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());
迪伦·劳伦斯(Dylan Lawrence)

您仍然会这样写,O(n)因为Big-O是最坏的情况(这里是线性时间)。在这种情况下n,当然是数组长度。从理论上讲,循环内什么都没有超出O(1)(我将忽略列表追加并将其称为常量。)

在注意到您对n/2迭代的评论之后n/2与说相同(1/2)nO((1/2)n)等同,O(n)因为在使用Big-O进行边界时我们忽略了所有系数。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章