首页 > 其他分享 >sicp每日一题[2.72]

sicp每日一题[2.72]

时间:2024-11-07 18:42:30浏览次数:1  
标签:2.71 每日 2.72 sicp number needed steps Exercise

Exercise 2.72

Consider the encoding procedure that you designed in Exercise 2.68. What is the order of growth in the number of steps needed to encode a symbol? Be sure to include the number of steps needed to search the symbol list at each node encountered. To answer this question in general is difficult. Consider the special case where the relative frequencies of then symbols are as described in Exercise 2.71, and give the order of growth (as a function of n) of the number of steps needed to encode the most frequent and least frequent symbols in the alphabet.


这道题如果只考虑 2.71 的那种情况,最常用的符号永远只需要1位,时间复杂度是 O(1), 最不常用的符号根据 2.71 的图可以看出来,每增加一个符号,所增加的步骤只是常数个,所以时间复杂度应该是 O(n)。

标签:2.71,每日,2.72,sicp,number,needed,steps,Exercise
From: https://www.cnblogs.com/think2times/p/18533761

相关文章

  • 算法每日双题精讲——双指针(移动零,复写零)
    ......
  • 使用 vscode 简单配置 ESP32 连接 Wi-Fi 每日定时发送 HTTP 和 HTTPS 请求
    最新博客文章链接文字更新时间:2024/11/07由于学校校园网,如果长时间不重新登陆的话,网速会下降,所以想弄个能定时发送HTTP请求的东西。由于不想给路由器刷系统,也麻烦。就开始考虑使用局域网内的服务器,不过由于服务器没有Wi-Fi模块,也不想搞USB无线wifi网卡,就想着干脆用单......
  • sicp每日一题[2.71]
    Exercise2.71SupposewehaveaHuffmantreeforanalphabetofnsymbols,andthattherelativefrequenciesofthesymbolsare1,2,4,...,2n1.Sketchthetreeforn=5;forn=10.Insuchatree(forgeneraln)howmanybitsarerequiredtoencode......
  • 20241107,LeetCode 每日一题,使用 Go 计算两数相加
    思路模拟加法:链表存储的是逆序数位,因此从头节点开始,逐位相加可以模拟正常的加法。每两个节点的值相加,并记录进位。逐节点相加:创建一个新的链表,用于存储结果,每次将两个链表对应节点的值加上进位值,结果存储到新链表的节点中。计算过程中,将(l1.Val+l2.Val+carry)相加的......
  • 20241107,LeetCode 每日一题,使用 Go 计算两数相加
    思路模拟加法:链表存储的是逆序数位,因此从头节点开始,逐位相加可以模拟正常的加法。每两个节点的值相加,并记录进位。逐节点相加:创建一个新的链表,用于存储结果,每次将两个链表对应节点的值加上进位值,结果存储到新链表的节点中。计算过程中,将(l1.Val+l2.Val+carry)相加的结......
  • LeetCode每日一题--3254.长度为k的子数组的能量值I
    代码解释:初始化结果数组:ans初始化为-1,因为如果子数组不满足条件,其能量值即为-1。连续递增子序列长度计数:cnt用于记录当前连续递增子序列的长度。遍历数组:使用enumerate遍历nums,同时获取元素的索引i和值x。更新连续递增子序列长度:如果当前元素是数组的第一......
  • sicp每日一题[2.70]
    Exercise2.70Thefollowingeight-symbolalphabetwithassociatedrelativefrequencieswasdesignedtoefficientlyencodethelyricsof1950srocksongs.(Notethatthe“symbols”ofan“alphabet”neednotbeindividualletters.)A2GET2SHA3......
  • 蓝桥杯每日一练--搜索旋转排序数组
    目录一、题目二、分析三、代码一、题目整数数组 nums 按升序排列,数组中的值 互不相同 。在传递给函数之前,nums 在预先未知的某个下标 k(0<=k<nums.length)上进行了 旋转,使数组变为 [nums[k],nums[k+1],...,nums[n-1],nums[0],nums[1],...,nums[k-1]](......
  • 每日OJ题_牛客_相差不超过k的最多数_滑动窗口_C++_Java
    目录牛客_相差不超过k的最多数_滑动窗口题目解析C++代码Java代码牛客_相差不超过k的最多数_滑动窗口相差不超过k的最多数_牛客题霸_牛客网(nowcoder.com)描述:        给定一个数组,选择一些数,要求选择的数中任意两数差的绝对值不超过 k 。问最多能选择多少......
  • sicp每日一题[2.69]
    Exercise2.69Thefollowingproceduretakesasitsargumentalistofsymbol-frequencypairs(wherenosymbolappearsinmorethanonepair)andgeneratesaHuffmanencodingtreeaccordingtotheHuffmanalgorithm.(define(generate-huffman-treepairs)......