关于Big(O)表演的问题
所以我的数据结构类涵盖了时间复杂度，我只是有一个关于数组列表和树状图性能的简单问题。
ArrayList 的 get 方法是 O(1)，TreeMap 的 get 方法是 o(log n)
现在，如果我创建一个循环遍历整个列表或树（例如
for (int i = 0; i < blahblah.size(); i++)
{
blah blah
}
For arraylist），那么这个循环性能是否为 o(1 ) 或 o(n)？我意识到当你检索 1 个项目时，性能是 O(1) 但这个循环会遍历整个列表，所以不是 1 * n 个项目会使其成为 n 吗？
与树形图相同的是，它是 o(log n) 或 n log n，因为您要遍历整个树。
so my data structure class is covering time complexity and I just have a quick question about the performance for arraylist and treemap.
The get method for ArrayList is O(1) and the get method for TreeMap is o(log n)
Now, if i made a loop that iterates through the entire list or tree such as
for (int i = 0; i < blahblah.size(); i++)
{
blah blah
}
For arraylist, would this loop performance be o(1) or o(n)? I realize that when you are retrieving 1 item, the performance is O(1) but this loop goes through the entire list so wouldn't it be 1 * n items which would make it n?
Same thing with the treemap would it be o(log n) or n log n since you're going through the entire tree.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
由于您需要数据结构的所有 n 个元素，因此结果不仅取决于给定的数据结构，还取决于您要检索的元素数量。
所以是的，结果将是 O(n) 或 O(n log n)，但根据数据结构，你可以做得更好。考虑一个链表——不用 O(n * n)，你可以用 O(n) 来完成。
但实际上，影响性能的不仅仅是大 O 常数。一个例子是 32 位数字的基数排序。用于排序的 O(n) 听起来很棒，但对于最合理的输入大小，快速排序肯定会更快。
Since you want all n elements of the data structure, the result is not just dependent of the given data structure but also of the number of elements you want to retrieve.
So yes the result would be O(n) or O(n log n), but depending on the data structure you could do better. Consider a linked list - instead of getting O(n * n) you can do just fine with O(n).
But then there's more to performance than just big O - constants do matter in reality. One example would be radix sort of 32bit numbers. O(n) for sorting sounds great, but a quick sort will be most certainly still be faster for most reasonable input sizes.
“ArrayList 的 get 方法是 O(1)，TreeMap 的 get 方法是 o(log n)”
ArrayList.get() 之所以是 O(1) 是因为通过索引查找只是相对于原点的偏移量。无论数组有 5 个还是 5M 个元素，工作量都是相同的。
TreeMap.get() 的复杂度为 O(log n)，因为它可能需要在二叉树中向下遍历多个元素。
"The get method for ArrayList is O(1) and the get method for TreeMap is o(log n)"
The reason ArrayList.get() is O(1) is because looking up by index is just an offset from origin. It doesn't matter if the array has 5 or 5M elements it's the same amount of work.
TreeMap.get() is O(log n) because it may have to traverse multiple elements downwards the binary tree.
是的，那就是 O(n)。 O 值几乎总是最坏的情况。
Yes, that would be O(n). O values are almost always worst case.
遍历所有元素的时间复杂度为
O(n)，因为您必须至少访问每个元素一次。出于同样的原因，无论您是按后序、中序还是前序访问节点，树状图都应该是
O(n)。Going through all elements would be
O(n)since you'd have to visit each at least once.The treemap should be
O(n)as well for the same reason regardles of whether you visit the nodes in postorder, inorder or preorder order.