摊余时间复杂度

文章/答案/技术大牛

发布

1回答

time-complexity

我正在研究一个问题，我们应该给出一个算法的例子，它的时间复杂度是O(n^2)，但其摊销时间复杂度低于O(n^2)。我马上想到的是嵌套循环，但我不太确定在结果被摊销的情况下会是什么样子的例子。

浏览 16提问于2021-03-20得票数 1

1回答

堆栈操作的摊余分析

algorithm、stack、time-complexity、amortized-analysis

我如何使用记账方法来证明，无论是否复制堆栈，每个堆栈操作都将具有O(1)的摊销复杂度？

浏览 8提问于2021-03-04得票数 0

1回答

std::map::erase() -哪个重载更快？

c++、map

map::erase()方法有两个重载来移除单个项：size_type erase ( const key_type& x );有人能证实吗？

浏览 7提问于2012-08-23得票数 3

回答已采纳

4回答

你能按O(n)分期复杂度对n个整数进行排序吗？

algorithm、complexity-theory、big-o

从理论上讲，是否可以按O(n)的摊余复杂度对n个整数的数组进行排序？目前的大多数算法都建立在O(nlogn)平均值+ O(n^2)最坏情况的基础上。

浏览 5提问于2011-05-25得票数 8

回答已采纳

2回答

Big-O:获取Java HashMap中的所有密钥

java、amortized-analysis

有人知道Java HashMap中keySet的摊余分析是什么吗？O(1) 正在遍历它们O(n)

浏览 2提问于2012-08-10得票数 0

回答已采纳

3回答

使用不相交集合的每个操作的摊销时间

big-o、disjoint-sets、amortized-analysis

我碰巧在维基百科上读到，不相交集合(并两个元素，找到特定元素的父元素)上的每个操作的摊余时间是O( a(n) )，其中a(N)是逆Ackermann函数，它增长非常快。有人能解释为什么这是真的吗？

浏览 7提问于2009-06-04得票数 2

1回答

摊余复杂度与最坏情况时间复杂度之间的关系

algorithm、complexity-theory、amortized-analysis

我有一组n个连续的操作，每个操作都以O(1)的摊销复杂度运行。我可以说整个集合运行在O(n)最坏情况下的时间复杂度吗？我该怎么证明呢？

浏览 0提问于2012-06-20得票数 0

回答已采纳

1回答

摊余成本与最坏情况

algorithm、amortized-analysis

例如，如果我们有一个O(1)的摊余成本，并进行m次操作，这将是O(m)的成本。我们是否可以说，对于m个操作，最坏的情况是O(m)*m？

浏览 22提问于2021-02-07得票数 2

回答已采纳

1回答

为什么Ackermann函数与用于不相交集合的联合查找算法的摊余复杂性有关？

set、complexity-theory、ackermann

谁能给我一个直观的解释，为什么阿克曼函数与用于不相交集合的并集查找算法的摊余复杂性有关我也在算法导论中查过，但它似乎也太严谨和不直观。

浏览 5提问于2011-06-14得票数 11

回答已采纳

2回答

使用会计方法的摊余时间成本

algorithm、methods、time-complexity、account、amortized-analysis

我认为我已经适当地确定了O(n)的最坏情况时间成本，其中n是数组中元素的数量。然而，我知道如果你使用“摊销成本”，你会发现平均情况下，时间成本可以准确地显示为O(1)。

浏览 2提问于2012-03-05得票数 2

回答已采纳

1回答

将树节点添加到向量向量中的n元树遍历的平均和最坏情况的时间复杂度是多少？

c++、time-complexity

我正在努力理解这个算法的时间复杂性。1)我知道深度优先搜索在图上的时间复杂度是O(V + E)，在二叉树上，因为边的数量是节点的两倍，所以我们可以将其推广到O(V)。然而，我们可以在n元树上做同样的假设吗？2)我知道push_back()的时间复杂度是一个摊余常数，但我们至少|V|次(树中的每个Node*一次)。那么Node*到current_vector的push_back()和current_vector到return_vector的push_back()会如何影响

浏览 10提问于2020-01-27得票数 0

回答已采纳

2回答

遍历给定大小的所有树

algorithm、math、graph、brute-force

我经常遇到通过暴力检查给定大小的树(图)的某些属性的问题。你有什么好的窍门吗？理想情况下，我只想检查每个同构类一次(但毕竟，速度才是最重要的)。对于n个节点上的树，我要求比“循环遍历所有(n-1)个-edge子集并检查它们是否形成树”之类的算法稍微更精细一些。

浏览 5提问于2011-02-14得票数 3

回答已采纳

1回答

List.Add的渐近复杂性是什么？

c#、algorithm、asymptotic-complexity

但是，每个时间列表都没有空间。这使得n元素所需的大小与log(n)成正比。List.Add()的真正基准值在以下。

浏览 2提问于2016-05-26得票数 7

回答已采纳

1回答

具有摊销复杂性需求的修改函数与具有非摊销复杂性需求的修改函数是什么？

language-agnostic、time-complexity、language-lawyer、complexity-theory

“常量”(非变异)函数(观察者或"getters")是否具有摊余的复杂性？编辑:澄清明显令人困惑的“观察者”(根据上下文，它可以意味着观察功能或外部观察者)。

浏览 21提问于2019-11-02得票数 1

4回答

Haskell中的高效队列

algorithm、data-structures、haskell、list、queue

我如何有效地实现一个列表数据结构，其中我可以有两个视图到列表的头部和结尾，它们总是指向列表的头部和尾部，而不需要代价高昂的调用来反转。即：end x = reverse start -- []end start1 -- [3,2,1]

浏览 0提问于2009-11-16得票数 27

回答已采纳

2回答

LinkedList与HashMap的摊销性能

performance、algorithm、data-structures、computer-science

对于大多数操作，哈希表的摊余性能通常被认为是O(1)。比方说一个标准的LinkedList实现，搜索操作的分期性能是多少？是O(n)吗？

浏览 1提问于2013-02-19得票数 1

回答已采纳

1回答

如何有效地将节点添加到分段树中进行最小范围查询？

c++、minimum、segment-tree

我有一个对象T的向量，我想在给定的范围内找到一个最小值。我实现了分段树来进行有效的搜索。如果我知道我将交替使用push_back、pop_back和query，那么更新树的有效方法是什么？是否需要在每个push_back和pop_back之后重新计算段树？我想接近O( log )。树的构建灵感来自于这个https://www.geeksforgeeks.org/iterative-segment-tree-range-minimum-query/。谢谢。简化版： ...

浏览 21提问于2021-05-01得票数 0

3回答

分配数组指针c++等价代码

c++、arrays、pointers

我正在修改我在C++对象中发现的一些代码。Message是一个c++类。unsigned char fifoQueue[256 * sizeof(Message)] = {0};///in headerfifoQueue = new unsigned char[256 * sizeof(Message)]; 不知何故，我不认为这是正确的。要获得相同的结果，正确的实现是什么？我只是对它的工作原理有点模糊--在给定的例子中，fi

浏览 0提问于2012-02-01得票数 0

回答已采纳

1回答

在elogv时间内实现dijkstra算法

c++、algorithm

在3b中，我们需要检查u的每个相邻顶点v，检查v是否为minHeap，minHeap是否支持这样的恒定时间操作，堆是最差的搜索数据结构，无论它是否在最小堆中，它都应该花费线性时间进行搜索，而且我们必须更新相邻顶点，所以我们不仅应该知道它是否在minHeap中，甚至还应该知道它的位置，以便我们可以更新它，我们希望所有这些都在logv时间内发生，否则就没有快速实现的点。

浏览 0提问于2014-06-17得票数 0

1回答