Kata03:目算能力

Kata03地址

顾名思义,目算就是用眼睛计算。

我不是阳炎厨千万别炸我啊。

目算通常是在编写代码前设计方案的时候发动,主要目的是估算程序需要运行的时间和需要占用的空间,并以此作为方案评估的标准之一。

这个Kata就是在锻炼目算,所以很高兴我们又不用写代码了。

Kata中提出了两类问题:How Big和How Fast,也就是计算空间和时间,下面分别列出题目内容。

How Big?

  • 下面这些无符号数字大约需要占用多少二进制位?
    • 1,000
    • 1,000,000
    • 1,000,000,000
    • 1,000,000,000,000
    • 8,000,000,000,000
  • 我的家在东北松花江上啊,那里大约有20000居民,如果每个居民都需要存储姓名、地址和电话号码的话,需要多少空间?所有数据都存为字符形式。
  • 要把一百万个整数存入二叉树,大约需要多少个节点?二叉树大约有几层?如果系统是32位,大约需要多少存储空间?

How Fast?

  • MFC Windows程序设计大约有1200页,用我家56k的铁通宽带传需要多长时间?
  • 我的二分查找算法处理一万个元素大约需要4.5秒,处理十万个元素大约需要6秒,那处理一千万个元素需要多长时间?(假设空间足够)
  • (这段原文太长我只提取中心思想)假设要破解最长为16位的密码,每位有96种可能性,尝试一次需要1ms,破解出来大约要多长时间?

知识点

这些内容没有标准答案,关键是思路。我说几个我认为比较关键的知识点供大家参考:

  • 1字节(1B)=8个二进制位(1b),1个字=4字节=32个二进制位,双字=8字节=64个二进制位
  • 字符按照编码方式不同占用长度不同,一般英文字符一个占1字节,汉字一个占2字节,大家估算一下即可
  • 二叉树中每个节点至少要有三个内容:数字和两个指针,两个指针分别指向左右孩子节点,所以告诉你32位系统的目的就是计算指针长度
  • MFC Windows程序设计这本书我真有,而且真超过了1000页,不过好像没到1200页,不要在意细节
  • 二分查找复杂度logn,算的时候别直接用比例算
  • 破解密码的话,MD5理论上无法逆推,但是有各种MD5反查网站,他们会正向计算各种常见密码的MD5,然后等你查的时候如果他们计算过就知道密码是什么了
  • 通用的密码破解方法是彩虹表,和反查MD5原理一样,暴力计算出所有可能性。不过彩虹表这东西极其大,我上初中的时候电脑硬盘只有40G,当时常用的彩虹表已经过百G了。
  • 我真不是阳炎厨

KB,MB,GB,KiB,MiB,GiB的区别

最后补充一个大知识点。

很多人都遇到过这种情况,买硬盘或者U盘,写着64G120G,回家一插电脑上发现实际容量会小一点,大家可能不太在意,觉得这是自带的一些存储内容占用了空间。其实不是这样,这是厂家耍的一个小把戏。

我们常说的KB,MB,GB,计算的时候是以10为底的,也就是说1KB其实就等于1000B,但是KiB,MiB,GiB是以2为底的,所以1KiB=1024B,也就是说KB,MB和GB实际上是小于KiB,MiB和GiB的。

厂家标容量的时候都是用KB,MB,GB,但是计算机实际使用的是KiB,MiB和GiB,所以你买的硬盘实际容量会比你想象的小一些。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容