普林斯頓Algorithms-1.4-演算法分析
時間分析
本節以一個常見的演算法題：
3sum 為例闡述演算法分析的過程：
科學家理解自然世界的方法對研究計算機程式的執行時間同樣有效：
Observe some feature of the natural world, generally with precise measurements.
Hypothesize a model that is consistent with the observations.
Predict events using the hypothesis.
Verify the predictions by making further observations.
Validate by repeating until the hypothesis and observations agree.
Observations.
Our first challenge is to determine how to make quantitative measurements of the running time of our programs. Stopwatch.java is a data type that measures the elapsed running time of a program.
最簡單的實現方法，複雜度 N^3.
Stopwatch⏲，每次double
Mathematical models.
The total running time of a program is determined by two primary factors: the cost of executing each statement and the frequency of execution of each statement.
波浪號近似
Designing faster algorithms.
One of the primary reasons to study the order of growth of a program is to help design a faster algorithm to solve the same problem. Using mergesort and binary search, we develop faster algorithms for the 2-sum and 3-sum problems.
2-sum. The brute-force solution TwoSum.java takes time proportional to N^2. TwoSumFast.java solves the 2-sum problem in time proportional to N log N time.
N log N
3-sum. ThreeSumFast.java solves the 3-sum problem in time proportional to N^2 log N time.
N^2 log N
空間分析
To estimate how much memory our program uses, we can count up the number of variables and weight them by the number of bytes according to their type. For a typical 64-bit machine,
Primitive types. the following table gives the memory requirements for primitive types.
Objects. To determine the memory usage of an object, we add the amount of memory used by each instance variable to the overhead associated with each object, typically 16 bytes. Moreover, the memory usage is typically padded to be a multiple of 8 bytes (on a 64-bit machine).
一個物件佔用的記憶體 = 例項變數佔用記憶體 + 物件本身開銷（指向物件類的引用 ，垃圾收集資訊，同步資訊）
另外還有填充位元組來佔位，因為記憶體的分配都是8的倍數（64位機器）
References. A reference to an object typically is a memory address and thus uses 8 bytes of memory (on a 64-bit machine). 指向物件的引用是8個位元組
Linked lists. A nested non-static (inner) class such as our Node class requires an extra 8 bytes of overhead (for a reference to the enclosing instance).
Arrays. Arrays in Java are implemented as objects, typically with extra overhead for the length. An array of primitive-type values typically requires 24 bytes of header information (16 bytes of object overhead, 4 bytes for the length, and 4 bytes of padding) plus the memory needed to store the values.
Strings. A Java 7 string of length N typically uses 32 bytes (for the String object) plus 24 + 2 N bytes (for the array that contains the characters) for a total of 56 + 2 N bytes.
Depending on context, we may or may not count the memory references by an object (recursively). For example, we count the memory for the char[] array in the memory for a String object because this memory is allocated when the string is created. But, we would not ordinarily count the memory for the String objects in a StackOfStrings object because the String objects are created by the client.