使用链表在堆栈中插入n个元素的时间复杂度是多少？

| 堆栈中的每次插入均为O（1），因此插入\'n \'个元素所需的时间为O（n）吗？ 我们也可以为哈希表说类似的话吗？通常情况下，在哈希表中插入\'n \'元素所需的时间= O（n）？     
2020-02-08 3 条评论
分享

没有找到相关结果

    已邀请:

    捕暑句簿姓

            是。决定性的因素不是插入时间，它是恒定的，而是迭代要插入的所有内容所花费的时间。如果插入不是在固定时间内进行的，则将更加复杂。 请注意，在HashTable的情况下，很大程度上取决于HashTable在发生这种情况时是否必须自行增长或重新哈希其中的所有内容，但对于简单情况（即假设表足够大以容纳所有内容，并且不会生成哈希码）碰撞）插入的上限应为n。     
    2020-02-08 0 0
    分享

    磨标烫徽啪

               堆栈中的每次插入均为O（1），因此插入\'n \'个元素所需的时间为O（n）吗？   我们也可以为哈希表说类似的话吗？通常情况下，   在哈希表中插入\'n \'元素= O（n）？ 如您所提到的stack，我假设我们使用栈（以链接的方式，使用封闭式寻址）解决哈希表中的冲突。 在这种情况下，我回答： 是的，\“在哈希表中插入\'n \'元素的平均时间= O（n）\”。 更加具体。由于插入到哈希表中是： 使哈希= O（1） 插入使用hash = O（1）选择的堆栈中 整个散列插入为O（1）。所以n个运算是O（n）。 我的建议：关于您的假设（您使用的结构，其实现和复杂性），在考试中要非常具体，因为所有这些细节可能会对所有方程式的结果产生重大影响。     
    2020-02-08 0 0
    分享
    为什么被折叠? 0 个回复被折叠

    要回复问题请先登录或注册

    或代码 OrCode.com 备案号：粤ICP备15020848号-1
    Escape time: 0.037765026092529