Java大O性能
我有一个关于我的课堂项目表现的问题。
我有大约5000个游戏对象是通过读取文本文件形成的。我有一个Treemap (称为超级树)，它的节点包含Treemaps (我猜是迷你树状地图)。这些nodes/mini treemaps是动作，策略，冒险，体育，游戏标题等。基本上游戏类型和这些迷你树将容纳游戏对象。因此，supertree本身可能容纳8 nodes/treemaps。
当我插入一个游戏对象时，它将确定它将进入哪个mini tree，并将其放入其中。例如，如果我插入游戏超级马里奥世界，它将检查它是哪种类型，并看到它是adventure，所以超级马里奥世界将插入到adventure树。
所以我的问题是，如果问题列出了所有的action games，那么性能如何，因为树状图get是O(log )。
首先，在超级树上，它将查找Action Node/Treemap，它将接受O(log )。
然后，一旦进入Action treemap，它就会得到所有元素，这些元素都是o(n log )，对吗？
那么log n * (n * log n)的总体性能是正确的吗？这比o(n)更糟糕。
编辑希望这澄清了我的帖子一点。
回答 2
Stack Overflow用户
发布于 2011-03-09 19:29:49
关于“任择议定书”分析的几点评论：
我假设您已经构建了树映射/集，并且只是从已完成的(预处理)内存表示中提取元素。
假设n是体裁的数目。假设m是每种类型游戏的最大数量。
获得正确的“体裁图”的复杂性是O(lg n) (超级树的单个get )。在这类游戏中迭代游戏的复杂性取决于你是如何做到的：
for (GameRef g : submap.keySet()) {
// do something with supermap.get(g)
}这段代码产生了O(m) 'get‘操作，每个操作都具有O(lg m)复杂性，所以这就是O(m lg(m))。
如果你这样做：
for (Map.Entry e : submap.entrySet()) {
// do something with e.getValue()
}然后，复杂性是O(m)循环迭代，具有恒定的(O(1))时间访问该值。
使用第二个map迭代方法，您的总复杂度是O(lg(n) + m)。
Stack Overflow用户
发布于 2011-03-09 19:17:55
呃，你是对的，直到最后一段。
您的总复杂性是O(n logn)，logn查找类型，n列出该类型中的所有值。
如果您要列出所有内容，那么肯定不是O(n^2 logn)，因为树中的所有值都是线性的。这将是O(n^2)。
使用平面列表做同样的事情将是O(n logn)，因此使用树肯定会导致性能下降(更别提内存了)。
https://stackoverflow.com/questions/5250904
复制相似问题
腾讯云开发者
