Memory Bit. 0 or 1. Byte. 8 bits. Megabyte (MB). 1 million or $2^{20}$ bytes. Gigabyte (GB). 1 billion or $2^{30}$ bytes. 64-bit machine. We assume a 64-bit machine with 8 byte pointers (References). ・Can address more memory. ・Pointers use more space (some JVMs “compress” ordinary object pointers to 4 bytes to avoid this cost). Typical memory usage for primitive types and arrays primitive types (bytes): boolean 1 byte 1 char 2 int 4 float 4 long 8 double 8...
假如有两种交税方式： 每天付 3 金币 每次付的金币呈指数级增长，但通知付款频率呈指数级下降 第1天：付 1 第2天：付 2 (累计 3) 第4天：付 4 (累积 7) 第8天：付 8 (累积 15) 哪种付的钱比较少？ 第二种比较划算，本质上等同于每天付 2，就是amortized constant。 A more rigorous examination of amortized analysis is done here, in three steps: Pick a cost model (like in regular runtime analysis) Compute the average cost of the i’th operation Show that this average (amortized) cost is bounded by a constant. 类似的应用在Array list 扩容中提到的 geometric resizing 方法(实际也是Python list 使用的方法)有体现, 所以使用一个因数来扩容数组, 可以让 ArrayList 的 add操作变为 amortized constant time....
Resource and Reference: CS61B Berkeley - Josh Hug Algorithms Princeton - ROBERT SEDGEWICK, KEVIN WAYNE 效率来源两个方面: 编程成本: 开发程序需要多长时间？代码是否容易阅读，修改和维护（大部分成本来自维护和可扩展性）？ 运行成本: 程序需要多长时间运行 (Time complexity)？ 需要多少内存 (Space complexity)？ Asymptotic Analysis Care about what happens for very large N (asymptotic behavior). We want to consider what types of algorithms would best handle scalability - Algorithms that scale well have better asymptotic runtime behavior. Simplification Summary Only consider the worst case. Pick a representative operation (aka: cost model) Ignore lower order terms Ignore multiplicative constants....
Hello World 参考了伯克利 Josh Hug 的 cs61b spring 2017 和 cs61b spring 2018. Lab, homework 和 project 代码实现参考 https://github.com/ShootingSpace/cs61b-data-structures. Java安装与配置 安装Java，前往Oracle下载java sdk，我用的是Java SE 8u151/ 8u152 版本。安装sdk时会同时安装sdr。 Windows系统配置: 推荐安装git bash, 一切按照默认安装就好. 更新系统环境变量: 直接在运行中搜索Environment Variables, 选择编辑系统环境变量, 在弹出的框中选择高级->环境变量, 在弹出的框中系统变量里面 新建变量: 变量名 = JAVA_HOME, 变量值 = 你的jdk路径,如C:\Program Files\Java\jdk1.8.0_151 编辑Path: 在前面加入%JAVA_HOME%\bin;%PYTHON_HOME%;(请注意，不能有空格.) OS X系统配置: 安装Homebrew，一个非常好用的包管理工具。要安装，请在terminal终端输入ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"(注意：在此过程中，可能会提示输入密码。当输入密码时，终端上不会显示任何内容，但计算机还是会记录你的密码的。这是一个安全措施, 让其他人在屏幕上看不到你的密码。只需输入您的密码，然后按回车。) 然后，通过输入以下命令来检查brew系统是否正常工作brew doctor. 如果遇到警告，要求下载命令行工具，则需要执行此操作。请参考这个StackOverflow。 安装git：输入brew install git 安装并配置好java后，测试是否成功: 随便在你喜欢的文件夹里新建一个java文件HelloWorld.java public class HelloWorld { public static void main(String[] args) { System....