插入到堆的时间复杂性
我主要是想理解在堆中插入一个新元素的大O和Omega背后的原因。我知道我可以在网上找到答案，但我真的喜欢有一个彻底的理解，而不是仅仅在网上找到答案，只是一味地记忆。
例如，如果我们有以下堆（以数组格式表示）
[8,6,7,3,5,3,4,1,2]
如果我们决定插入一个新元素“4”，那么我们的数组现在将如下所示
[8,6,7,3,5,3,4,1,2,4]
它将被放置在索引9中，由于这是第0个基于索引的数组，它的父数组将是索引4，也就是元素5。在这种情况下，我们不需要做任何事情，因为4是<5，并且它不违反二进制堆属性。所以最好的情况是OMEGA(1)。
但是，如果我们插入的新元素是100，那么我们将不得不调用max-heapify函数，该函数的运行时间为O（log n)，因此在最坏的情况下，在堆中插入新元素需要O（log n）。
共有1个答案
是的，关于最佳情况运行时间，您是对的。对于最坏的运行时间，您也正确地认为这是Theta（lg n），其原因是您的堆总是被假定为平衡的，即每个高度级别的节点集都是满的，除了底部级别。因此，当您在底层插入一个元素并在堆中从一个级别交换到下一个级别时，该级别上的节点数量大约减少了一半，因此在到达根节点（即堆顶部只有一个节点的级别）之前，您只能进行此交换log2(n)=O(lgn)次。如果您插入了一个属于堆顶部的值，首先是堆底部的值，那么您实际上必须进行log2(n)交换，才能将元素放到它属于的堆顶部。所以在最坏的情况下交换的数量是Theta（lg n）。
-
我对在LinkedList开头插入元素的时间复杂性感到好奇。我知道LinkedList本身会将现有元素向右移动一个索引，但要做到这一点，它会进行与列表中现有元素一样多的迭代吗？ 另外，最好的方式是在开头插入offerFirst吗？
-
我对这两种算法的时间复杂度感到困惑。 usingTreeMap算法的时间复杂度正确吗？我知道在treemap中插入时间是log(n ),但是如果我们遍历一个包含10个元素的数组，它会变成nlog(n)吗？
-
我偶然看到了这篇关于动态数组时间复杂性的文章，它澄清了很多。然而，我有一个基于案例的问题。假设我有一个总共有6个元素的动态数组，假设删除了第4个元素。在这种情况下，删除复杂度将是，这将是，因为最后两个元素只需要向上移动。这是正确的吗？我有一些文章给出了最坏情况下的复杂度，说如果删除最顶部的元素，那么时间复杂度将是。我找不到任何关于从中心移除/插入项目的内容。
-
主要内容：时间复杂度,空间复杂度《 算法是什么》一节提到，解决一个问题的算法可能有多种，这种情况下，我们就必须对这些算法进行取舍，从中挑选出一个“最好”的。 算法本身是不分“好坏”的，所谓“最好”的算法，指的是最适合当前场景的算法。挑选算法时，主要考虑以下两方面因素： 执行效率：根据算法所编写的程序，执行时间越短，执行效率就越高； 占用的内存空间：不同算法编写出的程序，运行时占用的内存空间也不相同。如果实际场景中仅能使用少量的内
-
我已经阅读了这么多的资源，但仍然无法理解什么是时间复杂性。我阅读的参考资料基于各种公式，我理解用于表示时间复杂性，但我不知道如何表示。谁能请解释这个原则，以一个可以理解的明确的方式请给我。
-
Wikipedia页面上关于二进制堆的声明是，在最坏的情况下插入是O（log n)，但平均为O(1)： 链接的页面试图如下说明： 但是，平均来说，新插入的元素在树中并不会移动很远。特别是，假设密钥分布均匀，它有一半的机会大于其父项；它有二分之一的机会比它的祖父母更大，因为它比它的父母更大；它有一半的机会比它的曾祖父母大，因为它比它的父母大，依此类推[...]因此在一般情况下插入需要恒定的时间 不过