newstarzl

动态 发布 点评 好友 关于
  • 2025-02-16

  • 发表了主题帖： 《Hello算法》学习笔记（一）-复杂度分析与数据结构

    本帖最后由 newstarzl 于 2025-2-16 21:59 编辑 首先感谢EEworld提供的试读机会，《HELLO算法》一书纸张厚实、印刷精美、图表丰富，阅读起来非常愉悦，更令人折服的是作者k神对计算机原理、数据结构、算法的深刻理解，从具象化的数据结构图解，到代码分步运行解析，一步步庖丁解牛，读后轻松地捋顺了很多令人困惑的知识点，是本难得的好书，本书的代码托管于GitHub - krahets/hello-algo: 《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 代码，且有电子书资源，目前，该书已在github上获得了109k星，在豆瓣上也获得了8.9的高分 现忙里偷闲，对书中的“干货”梳理一下，作为个人学习笔记，也希望能对初学的小伙伴有所提示： 1、迭代与递归 迭代：“自下而上”地解决问题：从最基础的步骤开始，然后不断重复或累加这些步骤，直到任务完成； 递归：“自上而下”地解决问题：将原问题分解为更小的子问题，这些子问题和原问题具有相同的形式，接下来将子问题继续分解为更小的子问题，直到终止条件满足时停止（终止条件的解是已知的）     上图可见，递归的缺点是显而易见的：时间和空间占用更多，更主要的是编程语言允许的递归深度通常是有限的，过深的递归可能造成栈溢出错误。 对于简单问题的求解，优选迭代，但对于复杂问题的求解，递归实现往往思路更直观、代码更简洁 尾递归：函数在返回前的最后一步才进行递归调用，函数体是放在形参里执行的，即在“递”的过程中完成了函数执行，“归”的过程仅需层层返回函数执行结果，这节约函数返回的堆栈临时数据空间，可达到和迭代相当的O（n）空间效率。 2、时间和空间复杂度 如上图显见： 时间复杂度按从低到高排列：常数阶（无迭代或递归）<对数阶（分治算法）<线性阶（单层迭代或递归）<线性对数阶（快速排序算法）<幂次阶（多层嵌套）<指数阶（多叉树）<阶乘阶（全排列） 空间复杂度按从低到高排列：常数阶（迭代）<对数阶（分治算法）<线性阶（递归）<平方阶（矩阵或图）<指数阶（多叉树） 时间复杂度和空间复杂度往往鱼和熊掌不可兼得，常常“以空间换时间” 3、编码 （1）整形数编码 “为什么整形类型数能表示的负数都比正数多一个？”k神首先抛出的这个问题，看似基础，其背后的原因却很容易被人忽略 我们知道一个N位数据类型，其可表示的数是偶数（2**N）个，为了区分正数和负数，我们很容易想到用最高位作为符号位，这样正负数是一一对应的，但0也会产生两种表示方式：+0（b#00000000）和-0（b#10000000），在计算中造成歧义 为解决这一问题，引入了补码。以0为界，原码和其补码分别表示正负数，根据二进制的模态性，原码和其补码之和为0，把减法计算归一化为简单的加法计算，无需额外的逻辑判断和位处理，绝对是天才的想法。唯一的影响是，原来的-0（b#10000000）没有与之对应的原码，这就是那个多出来的负数。 （2）浮点数编码   浮点数数据结构如上图所示，其原理是用指数位表达极大的取值范围，再通过分数位二分法得到逼近真值的近似值，不得不说这也是一个天才的设计，但其缺点也是存在的，当浮点数的值越大，其与真值的偏差也越大 （3）字符编码 字符编码类似于字典，是通过二进制数查找与之映射的字符，该字典就是“字符集”，英文和常用字符由单字节的ASCII码定义就够了，但中文则需要更大的Unicode字符集来定义 为节约Unicode编码数据的长度，开发了支持可变长度编码的UTF-8字符集，该字符集以首字节最高位起始的1的个数来标识字符字节数，后续字节均以“10”开始，便于解析和校验。 以上就是《HELLO算法》一书讲在数据结构和算法之前的先导知识，读后受益匪浅，为k神点赞

  • 2025-01-14

  • 回复了主题帖： 读书活动入围名单：《hello算法》

    个人信息无误，确认可以完成阅读分享计划!

发布的帖子
回复过的帖子

最近访客

< 1/1 >

统计信息

已有8人来访过

  • 芯积分：5
  • 好友：--
  • 主题：1
  • 回复：1

留言

你需要登录后才可以留言 登录 | 注册

现在还没有留言

推荐博文