2012级--讨论记录 (第二学期)

2013年3月1日

[课件下载]

1. 计算问题与算法。
   • 计算问题：input + output + their relationship。
   • 算法：well-defined computational procedure for achieving an input-output relationship。
2. 好算法。
   • 要素：正确性、高效性、易实现性。
   • 设计流程：思路-->过程-->正确性-->效率。
3. 算法的正确性分析。
   • partially correct：基于checkpoint和invariant。
   • totally correct：partially correct + termination。
4. 算法的效率分析。
   • RAM的要素：数据类型、数据存储方式；指令类型、指令执行方式。
   • running time的计算：cost*times；best/worst/average case。
5. 算法效率的渐进表示法。
   • Theta, O和Omega的含义：基于集合；基于极限。
   • Theta vs. O：用O避免分情况讨论。
   • O vs. o：基于集合；基于极限。
   • 渐进表示法的比喻：大小关系；相似的性质，但无trichotomy。