顾名思义,目算就是用眼睛计算。
我不是阳炎厨千万别炸我啊。
目算通常是在编写代码前设计方案的时候发动,主要目的是估算程序需要运行的时间和需要占用的空间,并以此作为方案评估的标准之一。
这个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,所以你买的硬盘实际容量会比你想象的小一些。