为什么std：：list：：reverse具有O(n)复杂度？
共有1个答案
假设，反向可能是O(1)。这里（再次假设）可能有一个布尔列表成员，指示链表的方向当前与创建列表的原始方向是相同的还是相反的。
不幸的是，这将降低基本上任何其他操作的性能（尽管不改变渐近运行时）。在每个操作中，都需要参考一个布尔值来考虑是跟随链接的“next”还是“prev”指针。
由于这可能被认为是一个相对不常见的操作，因此标准（它不规定实现方式，只规定复杂性）规定复杂性可以是线性的。这允许“Next”指针始终明确地表示相同的方向，加快了常见情况的操作。
-
Redis zrank。 返回存储在key处的排序集中成员的排名，分数从低到高排序。排名（或指数）是基于0的，这意味着得分最低的成员排名为0。 为什么复杂度是O（log（N））？成员按分数排序，但zank按成员查询。 我找到了一些可能是答案的东西。 A.zset由ziplist实现时 大小小于128 每个成员的大小小于64字节 所以，ziplist的大小很小，所以这不是我讨论的问题。 B.当zse
-
问题内容： 我刚刚开始学习数据结构，并且在进行数组插入时想知道为什么数组插入的时间复杂度为O（n）而不是O（n + 1）？ 在最佳情况下，当插入在最后时，时间复杂度为O（1）。我想我们正在考虑1插入元素，因为这里没有元素被移动。在最坏的情况下，假设我们必须移动n个元素然后插入新元素，那么时间时间复杂度是否应该为O（n + 1）？n用于移动元素，1用于插入。 非常感谢您的帮助。 问题答案： O（n）
-
有一个循环执行蛮力算法来计算5*3，而不使用算术运算符。 我只需要加5 3次，这样它就需要O（3），如果输入是x*y，它就是O（y）。但是，在一本书中，它说它需要O（2^n），其中n是输入中的位数。我不明白为什么它用O（2^n）来表示它O（y）。这是显示时间复杂度的更好方法吗？。你能解释一下吗？ 我没有要求其他算法来计算这个。
-
我在GeekforGeekshttps://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/中检查“到达终点的最小跳跃次数”问题。我对这里提到的时间复杂度感到困惑，它是O（n^n）。 如果我看到上面的代码块，minJumps（arr，I，h）递归调用是从I=l1调用的。所以在每个递归步骤中，l（
-
算法相对较新，所以如果我遗漏了一些显而易见的东西，请原谅！ 我知道深度优先搜索的空间复杂度通常表示为O(h)，其中h是树的高度，而广度优先搜索的复杂度是O(n)，其中n是树中节点的数量。 我理解解释（例如在这个答案中https://stackoverflow.com/a/9844323/10083571)也就是说，在BFS中最坏的情况下，所有节点都在一个级别上，这意味着我们必须在遍历它们之前将所有
-
问题内容： 来自redis doc： ZPOPMIN键[count]自5.0.0起可用。 时间复杂度：O（log（N）* M），其中N为排序集中元素的数量，M为弹出元素的数量。 删除并返回存储在key排序集中的得分最低的成员。 因此，我的问题是，如果列表已排序，为什么要使用log n，为什么不使用O（1）？ 问题答案： 如果 列表 已排序，为什么要使用log n，为什么不使用O（1）？ 如果使用列