-
1 votesanswersviews
将元素插入此结构的摊销时间复杂度是多少？
假设您使用数组实现堆，并且每次数组已满，您将其复制到其大小的两倍的数组 . 将元素插入堆中的摊销时间复杂度（最坏的情况）是多少？ 我认为我们有 T(n) = n * n （这是最坏情况下n个操作序列的总成本的上限），然后根据一个公式的摊销复杂度是 T(n) / n = n^n / n = n . 但我认为这是非常错误的，因为从直觉上可以清楚地知道我应该得到 log(n) 或更低......所以我... -
0 votesanswersviews
使用最坏情况，平均情况或摊销分析的公约？
我理解为算法执行复杂性分析的不同情况的机制，但是已经给出了几个场景，并且已经被问到我将针对每种情况使用哪种类型的分析 . 分析类型是“最坏情况”，“平均情况”，“摊销” . 当然要确保算法尽可能高效，我们总是选择使用“最坏情况”？ 我意识到这是主观的，但使用每种分析方法肯定有优点吗？ 这是我在最近的一次面试中给出的4种情景，除了关于飞行员的情况之外，我们无法决定其中的任何情况 . 一家公司发明了... -
1 votesanswersviews
堆排序时间复杂性深刻理解
当我在大学学习数据结构课程时，我学到了以下公理： 在最坏的情况下将新数字插入堆需要 O(logn) （取决于作为叶插入时它到达树中的高度） 使用 n 节点构建一堆 n 节点，从空堆开始，使用摊销分析求和为 O(n) 时间 在最坏情况下删除最小值需要 O(logn) 时间（取决于新顶节点在与最后一个叶子交换后达到的低点） 逐个删除所有最小值，直到堆为空，需要 O(nlogn) 时间复... -
0 votesanswersviews
二元搜索的最坏情况复杂化
对于我们正在寻找的元素出现的2 ^ n-1个元素的排序数组的二元搜索，最终情况下的最终时间复杂度是多少？ 在我的评审表上找到了我的期末考试 . 我甚至无法弄清楚为什么我们要为二进制搜索分配时间复杂度，因为最坏的情况是O（log n） . 根据我的说明，摊销成本计算算法的上限，然后将其除以项目数，因此不会像最坏情况时间复杂度除以n那样简单，意味着O（log n ）/ 2 ^ N-1？ 作为参考，这是...