Big-O分析- While循环
Big-O分析- While循环
提问于 2014-11-01 02:04:50
我遇到了一个编程问题，给定一个数组，确定它是否是二叉树的后序遍历。我的解决方案如下：
public static boolean isPostOrder(int[] array) {
int root = array[array.length - 1];
int i = 0;
while(array[i] < root) {
i++;
}
while(array[i] > root) {
i++;
}
return i == array.length - 1;
}我正在尝试理解Big O。我已经阅读了这个教程：
What is a plain English explanation of "Big O" notation?
但是，我仍然对加法和while循环感到困惑。我假设在这种情况下，我的while循环是O(1)，因为我们只是将数组中的值与整数进行比较，或者我错了？
现在加法也是O( 1 )，因为我们只是将1加到某个整数1上，对吗？
因此，这是一个O(1)解决方案，还是我遗漏了什么？
回答 2
Stack Overflow用户
发布于 2014-11-01 02:11:58
您的算法运行时与输入大小具有线性连接，因为您遍历输入数组的元素。这使得你的算法是O(n)。如果你不会有任何循环，它将是O(1) =恒定的访问时间。
Stack Overflow用户
发布于 2014-11-01 02:13:18
Big-O符号背后的基本思想是估计算法执行的基本操作的数量，以及输入的大小如何影响它。
这里，您的基本操作是递增i (++i)。你正在迭代一个大小为N的数组，在最坏的情况下，你会遍历所有的数组。因此，该算法的复杂度为O(N)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/26680858
复制相关文章
相似问题
腾讯云开发者
