专栏首页架构说建堆时间复杂度是o(n)

建堆时间复杂度是o(n)

how-can-building-a-heap-be-on-time-complexity

前言:换个马甲你不认识了。

  • 当面试问过上学时候,有没有学习数据结构?
  • 他考察范围课本上知识,而不是leecode刷题。
  • 因此基本知识自己看清楚。因为出现错误理解,浅显理解等 混淆理解,你完全卡在这里了。

后记:自己心里轻视,这么简单问题,还为 例如排序,数组,链表 tree 图特点 我已经完全掌握了,100%失败。

容易混淆的认知,当你决策时候傻傻分不清楚

堆的定义:是一个完全二叉树,但不是二叉搜索树,也不是平衡的二叉树

后记:完全二叉树特点经过一次教训你记住了 当前节点和子节点关心是i 和2i 2i+1。

然后你有被问到查找节点是只记得做小右大。有忘记了.大顶堆特点是 上层大于下层 下层,简单的 数学比较大小

  • 根据定义,你会发现,不是完全有序,只能从第一个节点获取最大值 或者最小值。优先级队列

忽视地方:

  1. 二叉搜索树子节点一定是left小,right大。
  2. 但是堆不确定。都大于/小于root,但是具体那个最大/最小。需要比较一下。

查找算法:查找最小一个值。

  • 二叉搜索树查找:
  1. 如果该值小于当前节点,取左分支。
  2. 如果该值大于当前节点,取右分支.
  3. 如果该值等于当前节点,找到了!

堆:有个步骤,建堆 和调整

  1. 建堆:Heap Building
  • 建堆的时间复杂度就是O(n)。

up_heapify()

down_heapify() https://afteracademy.com/blog/operations-on-heaps book上用法

With this assumption, level 0 of the tree has 1 node, level 1 has 2 nodes, and up to level h, which has 2h nodes. All the leaves reside on level h.

数学知识,你可以的,之前都学习过,给你30分钟 回想起来

  1. 删除堆顶元素:从root元素开始删除,删除后,,选择子节点最小元素进行交换,从下到上递归
  2. 插入元素:插入最后一个位置,选择和paret节点进行交互。
  3. 插入删除元素的时间复杂度也为O(log n)。

后记:链表基本操作 删除和删除,但是堆不一样,你遗忘记地方 建堆,然后基本操作删除和删除,这个之前根本没想道过建堆这个步骤。

Q2: Find-max (or Find-min) → find a maximum item of a max-heap, or a minimum item of a min-heap, respectively.

后记:

你只记得完全二叉树的第一个特点,忘记第二个特点(相对满二叉树)就是h ,h-1 层存在叶子节点 并且你做过怎判断一个tree是完全二叉树。在这里你忘记了。

时间复杂度:

(3)堆的插入、删除元素的时间复杂度都是O(log n);https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity

(4)建堆的时间复杂度是O(n);

(5)堆排序的时间复杂度是O(nlog n);

T(Heap Sort) = T(build Heap) + (N-1)*T(down_heapify)
             = O(N) + (N-1)*O(logN)
             = O(N) + O(NlogN)
             = O(NlogN)
                          
https://afteracademy.com/blog/heap-building-and-heap-sort
http://www.cs.umd.edu/~meesh/351/mount/lectures/lect14-heapsort-analysis-part.pdf

塔山之石

  1. 拜托,面试别再问我堆(排序)了!
  • https://www.cnblogs.com/tong-yuan/p/Heap.html
  • 每个字都看,看三遍,可以培养你耐心。
  • 即使你懂了也看。更加培养你耐心
  • 输出:开始中--
  1. 刷题理解
  • https://afteracademy.com/tech-interview/ds-algo-concepts/
  1. 完整课程
  • http://www.cs.umd.edu/~meesh/351/mount/lectures/lect14-heapsort-analysi s-part.pdf
  • http://www.cs.umd.edu/~meesh/351/mount/lectures/
  1. 刻意练习:
  • https://www.tutorialspoint.com/convert-min-heap-to-max-heap-in-cplusplus
  • 你一定每个题目做一次。
  • 输出:开始中--

http://tpcg.io/Te9Xc4e8

how-can-building-a-heap-be-on-time-complexity

本文分享自微信公众号 - 架构说(JiaGouS),作者:面向工作学习

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-05-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 时间复杂度O(n)和空间复杂度

    算法对于敲代码的应该都听过,不管是复杂的还是简单的,衡量算法效率的两个重要指标就是时间复杂度和空间复杂度。

    wade
  • 时间复杂度o(1), o(n), o(logn), o(nlogn)

    1、时间复杂度o(1), o(n), o(logn), o(nlogn)。算法时间复杂度的时候有说o(1), o(n), o(logn), o(nlogn),这...

    别先生
  • 【转】算法中时间复杂度概括——o(1)、o(n)、o(logn)、o(nlogn)

    在描述算法复杂度时,经常用到o(1), o(n), o(logn), o(nlogn)来表示对应算法的时间复杂度。这里进行归纳一下它们代表的含义:...

    用户5640963
  • java - 手写LRU(使用链表,时间复杂度O(n))

    夹胡碰
  • 每日一题:堆排序中建堆过程的时间复杂度是

    end

    程序员小王
  • Python-排序-有哪些时间复杂度为O(n)的排序算法?

    人到中年,容易变得油腻,思想懒惰,身体就容易发胖。为了摆脱中年油腻,不如和我一起学习算法来烧烧脑子,燃烧你的卡路里。

    somenzz
  • 将判断 NSArray 数组是否包含指定元素的时间复杂度从 O(n) 降为 O(1)

    NSArray 获取指定 元素 的位置 或者 判断是否存在指定的 元素 的时间复杂度是 O(n)(包含特定元素时,平均耗时是 O(n/2),如果不包含特定元素,...

    酷酷的哀殿
  • 时间复杂度中的log(n)底数到底是多少?

    假设有底数为2和3的两个对数函数,如上图。当X取N(数据规模)时,求所对应的时间复杂度得比值,即对数函数对应的y值,用来衡量对数底数对时间复杂度的影响。

    城市中的游牧民族
  • 在O(1)时间复杂度删除链表节点

    一份执着✘
  • 如何在O(1)时间复杂度下实现LRU

    通常我们会把频繁用到的数据放到缓存里,这样取数据比较快,但内存有限,所以经常会有一些淘汰策略,LRU就是其中一种,他的原理是:我们认为最近访问(包括 get 和...

    用户7685359
  • 算法素颜(第3篇):KO!大O——时间复杂度

    在本系列第1篇《走下神坛吧!算法》中提到了:计算复杂度分为时间复杂度与空间复杂度。本篇文章来讲讲时间复杂度。

    用户5224393
  • 漫画:什么是时间复杂度?

    场景1. 给小灰一条长10寸的面包,小灰每3天吃掉1寸,那么吃掉整个面包需要几天?

    用户1564362
  • BAT面试题43:log(n)时间复杂度下求n次幂

    https://blog.csdn.net/weixin_42292229/article/details/86742650

    double
  • 【算法复习3】时间复杂度 O(n) 的排序 桶排序 计数排序基数排序

    将要排序的数据分到几个有序的桶里, 每个桶里的数据再单独进行排序。 桶内排完序之后,再把每个桶里的数据按照顺序依次取出, 组成的序列就是有序的了。

    韩旭051
  • 任务的插入时间复杂度优化到 O(1),Timing Wheel时间轮是怎么做到的?

    来源 | https://www.jianshu.com/p/0f0fec47a0ad

    程序猿DD
  • 【go】剑指offer: 删除链表结点O(1)时间复杂度

    给定单链表的头指针和一个结点指针,定义一个函数在O(1)时间删除结点,链表结点与函数的定义如下:

    陌无崖
  • 究竟什么是时间复杂度,怎么求时间复杂度,看这一篇就够了

    我们该如何估计程序运行时间呢,我们通常会估计算法的操作单元数量,来代表程序消耗的时间, 这里我们默认CPU的每个单元运行消耗的时间都是相同的。

    代码随想录
  • 我们常说的算法时间复杂度和空间复杂度到底是什么?

    针对某一类问题的解决,我们可能需要借助算法来实现,实现的手段也可能是各式各样的。虽然最终都解决了问题,但是各个解决手段,也就是算法还是存在优劣之分的。

    隐逸王
  • 排序-线性排序,如何做到百万级数据秒级排序,时间复杂度O(n)?

    我们经常接触的冒泡排序,快速排序,归并排序等,这些排序时间复杂度大多是n^2或者N(logN),他们都是基于比较的排序(就是排序过程中数据两两做比较),那你有知...

    阿伟

扫码关注云+社区

领取腾讯云代金券