算法和数据结构

算法和数据结构应该说是计算机科学的基石，但对于绝大多数工程师而言，职业生涯能够选择和应用算法机会比较少，因为绝大数库都做了很好的封装和抽象，让工程师无感地做个调包侠，设计和开发算法的机会更是少之又少，尽管如此，还是感受一下大师们的智慧吧。

Analysis of Algorithm

• How long will my program take?
• Why does my program run out of memory?

Scientific Method

The very same approach that scientists use to understand the natural world is effective for studying the running time of programs:

• 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.

Essence of Math

The art of doing mathematics is finding that special case that contains all germs of generality.

Analyzing Running Time

Steps:

• Develop an input model, including a definition of the problem size.
• Identify the inner loop.
• Define a cost model that includes operations in the inner loop.
• Determine the frequency of execution of those operations for the given input.

References:

Analyzing Memory Usage

复杂对象分解成基础类型，基础类型所占的字节数相对固定，在此基础上累加计算。

Developing an Efficient Algorithm

• Decide on a complete and specific problem statement, including identifying fundamental abstract operations that are intrinsic to the problem and an API.
• Carefully develop a succinct implementation for a straightforward algorithm, using a well-thought-out development client and realistic input data.
• Know when an implementation could not possibly be used to solve problems on the scale contemplated and must be improved or abandoned.
• Develop improved implementations through process of stepwise refinement, validating the efficacy of ideas for improvement through empirical analysis, mathematical analysis, or both.
• Find high-level abstract representations of data structures or algorithms in operation that enable effective high-level design of improved versions.
• Strive for worst-case performance guarantees when possible, but accept good performance on typical data when available.
• Know when to leave further improvements for detailed in-depth study to skilled researchers and move on to the next problem.

Important and Useful Algorithms

• Bags, Queues, and Stacks
  • Implementations using resizing arrays and linked lists.
• Sorting
  • Elementary Sorts: Selection Sort, Insertion Sort, Bubble Sort and Shellsort
  • Mergesort
  • Quicksort
  • Priority Queues: One of implementations using binary heap.
• Searching
  • Symbol Tables: Key is original value.
  • Binary Search
  • Binary Search Tree
  • Balanced Search Tree
  • Hash Tables: Transform key with hash function.
• Graphs
  • Undirected Graphs
  • Directed Graphs
  • Depth First Search
  • Breadth First Search
  • Minimum Spanning Trees
  • Shortest Paths
• Strings
  • String Sorts
    • Key-indexed counting
    • LSD: Least-significant-digit string sorts, right-to-left order.
    • MSD: Most-significant-digit string sorts, left-to-right order.
    • Three-way string quicksort
  • Tries：R-way tries and ternary search tries for implementing symbol tables with string keys.
  • Substring Search
    • Brute-force substring search
    • Knuth-Morris-Pratt substring search
    • Boyer-Moore substring search
    • Rabin-Karp fingerprint search
  • Regular Expressions
    • DFA: Deterministic finite-state automation
    • NFA: Nondeterministic finite-state automata
    • 编译原理概述 - 前端 - 词法分析
  • Data Compression
    • Run-length encoding
    • Huffman compression: Maintain a table of variable-length codewords for fixed-length patterns in the input.
    • LZW compression: Maintain a table of fixed-length codewords for variable-length patterns in the input.
• Context
  • Event-driven simulation
  • B-trees
  • Suffix arrays
  • Network-flow algorithms
  • Reduction
  • Intractability

应付面试的思路就是刷题，有印象且记得住，还能写出来你就无敌了：