天道酬勤,学无止境

amortized-analysis

每次以固定常数增长动态数组的效率?(Efficiency of growing a dynamic array by a fixed constant each time?)

问题 因此,当每次添加元素时动态数组的大小加倍时,我理解扩展的时间复杂度是 O(n) n 作为元素。 如果数组被复制并移动到一个新数组,当它已满时,它的大小只有 1 倍怎么办? (而不是加倍)当我们通过某个常数 C 调整大小时,时间复杂度总是 O(n)? 回答1 如果你增加了一些固定的常数 C,那么不,运行时间不会是 O(n)。 相反,它将是 Θ(n 2 )。 要看到这一点,请考虑如果您执行一系列 C 连续操作会发生什么。 在这些操作中,C - 1 个将花费时间 O(1),因为空间已经存在。 最后一个操作将花费 O(n) 时间,因为它需要重新分配数组、添加空间并复制所有内容。 因此,任何 C 操作序列都需要时间 O(n + c)。 所以现在考虑如果你执行 n 个操作的序列会发生什么。 将这些操作分解成大小为 C 的块; 将有 n / C 个。 执行这些操作所需的总工作量将是 (c + c) + (2c + c) + (3c + c) + ... + (n + c) = cn / c + (c + 2c + 3c + ... + nc / c) = n + c(1 + 2 + 3 + ... + n / c) = n + c(n/c)(n/c + 1)/2 = n + n(n/c + 1)/2 = n + n 2 / c + n / 2 = Θ(n 2 )

2021-07-29 01:17:48    分类:技术分享    arrays   data-structures   big-o   time-complexity   amortized-analysis

Design a stack that can also dequeue in O(1) amortized time?

I have an abstract data type that can be viewed as a list stored left to right, with the following possible operations: Push: add a new item to the left end of the list Pop: remove the item on the left end of the list Pull: remove the item on the right end of the list Implement this using three stacks and constant additional memory, so that the amortized time for any push, pop, or pull operation is constant. The stacks have basic operations, isEmpty, Push, and Pop. Amortized time means "If I spend this amount of time, I can spend another block of it and store it in a bank of time to be used

2021-06-22 17:34:33    分类:问答    algorithm   stack   amortized-analysis

不相交集森林数据结构的联合/查找算法不按等级联合(Union/find algorithm without union by rank for disjoint-set forests data structure)

问题 以下是维基百科上不相交集森林的联合/查找算法的细分: 准系统不相交集森林... ( O(n) ) ...按等级合并...(现在改进为O(log(n) ) ... 路径压缩(现在改进为O(a(n)) ,有效地O(1) ) 按等级实现联合需要每个节点保留一个rank字段以进行比较。 我的问题是,按等级联合是否值得这个额外的空间? 如果我按等级跳过联合而只进行路径压缩,会发生什么? 够好吗? 现在的摊销复杂度是多少? 发表了一条评论,暗示没有路径压缩的按秩并集(摊销O(log(n)复杂度)对于大多数实际应用来说已经足够了。这是正确的。我要问的是另一种方式:如果你跳过并集怎么办按等级,只做路径压缩? 从某种意义上说,路径压缩是按等级改进联合的额外步骤,这就是为什么可以省略该额外步骤而不会造成灾难性后果的原因。 但是按等级联合是路径压缩的必要中间步骤吗? 我可以跳过它并直接进行路径压缩,否则会是灾难性的吗? 还有人指出,如果没有按等级联合,重复联合可能会创建一个类似链表的结构。 这意味着在最坏的情况下,单路径压缩操作可能需要O(n) 。 这当然会影响未来的运营,所以当在许多运营中摊销时,我更感兴趣的是它的表现。 回答1 我在 google 上搜索了“没有按等级划分的工会”,出现的第二个链接是这个: ...我们通过对带有路径压缩但没有按等级并集的联合查找进行分析来结束本节

2021-06-11 20:54:15    分类:技术分享    algorithm   data-structures   time-complexity   disjoint-sets   amortized-analysis

need to find the amortized cost of a sequence using the potential function method

There is a sequence of n operations, The ith operation costs 2i if i is an exact power of 2, costs 3i if i is an exact power of 3, and 1 for all other operations.Hi first up I want to say that it is a homework problem and I don't want you to solve it for me. I have solved it using the aggregate method. For which I summed up the series of powers of 2 and series of powers of 3 and got amortized cost of 10. I then checked it using the accounting method, for really long sequences and it did not fail. But my problem is how to prove that it would never fail, I can show for as long sequence I want

2021-06-10 14:08:52    分类:问答    algorithm   amortized-analysis

Efficiency of growing a dynamic array by a fixed constant each time?

So when a dynamic array is doubled in size each time an element is added, I understand how the time complexity for expanding is O(n) n being the elements. What about if the the array is copied and moved to a new array that is only 1 size bigger when it is full? (instead of doubling) When we resize by some constant C, it the time complexity always O(n)?

2021-06-02 17:00:00    分类:问答    arrays   data-structures   big-o   time-complexity   amortized-analysis

Union/find algorithm without union by rank for disjoint-set forests data structure

Here's a breakdown on the union/find algorithm for disjoint set forests on wikipedia: Barebone disjoint-set forests... (O(n)) ... with union by rank ... (now improved to O(log(n)) ... with path compression (now improved to O(a(n)), effectively O(1)) Implementing union by rank necessitates that each node keeps a rank field for comparison purposes. My question is, is union by rank worth this additional space? What happens if I skip union by rank and just do path compression instead? Is it good enough? What is the amortized complexity now? A comment is made that implies that union by rank without

2021-05-24 13:01:53    分类:问答    algorithm   data-structures   time-complexity   disjoint-sets   amortized-analysis

为什么python的list.append()方法的时间复杂度为O(1)?(Why is the time complexity of python's list.append() method O(1)?)

问题 从TimeComplexity文档中可以看出,Python的list类型是使用数组实现的。 因此,如果正在使用数组并且进行了一些附加操作,最终您将不得不重新分配空间并将所有信息复制到新空间。 毕竟,这是O(1)最坏的情况吗? 回答1 如果查看链接文档中的脚注,您会发现它们包含以下警告: 这些操作依赖于“最坏情况摊销”的“摊销”部分。 根据容器的历史记录,各个动作可能会花费惊人的时间。 使用摊销分析,即使我们偶尔需要执行昂贵的操作,当您将它们视为序列而不是单独进行操作时,我们也可以降低“平均”操作成本。 因此,任何单个操作都可能非常昂贵-O(n)或O(n ^ 2)或更大的值-但由于我们知道这些操作很少见,因此我们保证可以在准时。 回答2 摊销O(1),而不是O(1)。 假设列表保留大小为8个元素,当空间用尽时,它的大小增加了一倍。 您要推送50个元素。 前8个元素压入O(1)。 第九个触发重新分配和8个副本,然后进行O(1)推送。 接下来的7个推入O(1)。 第17个触发器触发重新分配和16个副本,然后进行O(1)推送。 接下来的15个推入O(1)。 第33个触发器触发重新分配和32个副本,然后进行O(1)推送。 接下来的17个推入O(1)。 因此,所有推送都具有O(1)复杂度,我们在O(1)有56个副本,在O(n)有3个重分配,n = 8、16和32。请注意,这是一个几何级数

2021-05-08 16:37:52    分类:技术分享    python   python-2.7   time-complexity   amortized-analysis

用外行的术语摊销复杂性?(Amortized complexity in layman's terms?)

问题 有人可以用外行的术语解释摊销的复杂性吗? 我一直很难在网上找到精确的定义,但我不知道它与算法分析完全相关。 任何有用的东西,即使从外部引用,也将受到高度赞赏。 回答1 摊销的复杂度是在一系列操作中评估的每次操作的总费用。 这个想法是要保证整个序列的总费用,同时允许单个操作的成本要比摊余成本高得多。 例子: C ++ std::vector<>的行为。 当push_back()将向量大小增加到其预先分配的值以上时,它将使分配的长度加倍。 因此,单个push_back()可能需要O(N)时间来执行(因为将数组的内容复制到新的内存分配中)。 但是,由于分配的大小增加了一倍,因此下一个对push_back() N-1调用将各自花费O(1)时间来执行。 因此,总共N操作仍将花费O(N)时间; 从而使push_back() O(1)每次操作的摊销成本为O(1) 。 除非另有说明,否则分摊的复杂度是任何操作序列的渐近最坏情况保证。 这表示: 与未摊销的复杂度一样,用于摊销的复杂度的big-O符号忽略固定的初始开销和恒定的性能因子。 因此,出于评估big-O摊销性能的目的,通常可以假定摊销操作的任何顺序将“足够长”以摊销固定的启动费用。 具体地说,对于std::vector<>示例,这就是为什么您不必担心是否会实际遇到N其他运算的原因:分析的渐近性质已经假定您会。 除任意长度外

2021-04-26 11:11:16    分类:技术分享    algorithm   amortized-analysis

摊销算法分析(Amortized Analysis of Algorithms)

问题 我目前正在阅读摊销分析。 我无法完全理解它与我们为计算算法的平均或最坏情况行为而进行的常规分析有何不同。 有人可以用排序示例或其他示例来解释它吗? 回答1 摊销分析给出了最坏情况下每个操作的平均性能(随时间变化)。 在一系列操作中,最坏的情况不会在每个操作中经常发生-一些操作可能很便宜,有些可能很昂贵,因此,传统的每个操作分析的最坏情况可能会带来过于悲观的局限。 例如,在动态数组中,只有一些插入需要线性时间,而其他插入则需要固定时间。 当不同的刀片花费不同的时间时,我们如何准确地计算总时间? 摊销方法将为序列中的每个工序分配“人为成本”,称为工序的摊销成本。 它要求序列的总实际成本应以所有工序的摊销成本总和为边界。 注意,分期摊销成本的分配有时会很灵活。 摊销分析中使用了三种方法 汇总方法(或蛮力) 会计方法(或银行的方法) 电位法(或物理学家的方法) 例如,假设我们正在对一个数组进行排序,其中所有键都是不同的(因为这是最慢的情况,并且与不使用它们的时间相同,如果我们不对等于枢)。 Quicksort选择一个随机枢轴。 枢轴也有可能是最小的键,第二个最小键,第三个最小键,...或最大的键。 对于每个密钥,概率为1 / n。 令T(n)是一个随机变量,它等于快速排序在n个不同键上的运行时间。 假设quicksort选择第i个最小键作为支点。 然后,我们在长度为i −

2021-04-24 04:12:19    分类:技术分享    algorithm   amortized-analysis

Amortized time of dynamic array

As a simple example, in a specific implementation of the dynamic array, we double the size of the array each time it fills up. Because of this, array reallocation may be required, and in the worst case an insertion may require O(n). However, a sequence of n insertions can always be done in O(n) time, because the rest of the insertions are done in constant time, so n insertions can be completed in O(n) time. The amortized time per operation is therefore O(n) / n = O(1). --from Wiki But in another book :Each doubling takes O(n) time, but happens so rarely that its amortized time is still O(1)

2021-04-19 02:36:41    分类:问答    algorithm   amortized-analysis