“2012级--讨论记录 (第二学期)”的版本间的差异
来自问题求解
(→2013年3月1日) |
(→2013年3月1日) |
||
第36行: | 第36行: | ||
<li>Theta vs. O:用O避免分情况讨论。</li> | <li>Theta vs. O:用O避免分情况讨论。</li> | ||
<li>O vs. o:基于集合;基于极限。</li> | <li>O vs. o:基于集合;基于极限。</li> | ||
− | <li> | + | <li>渐进表示法的比喻:大小关系;相似的性质,但无trichotomy。</li> |
</ul> | </ul> | ||
</li> | </li> | ||
</ol> | </ol> |
2013年2月28日 (四) 22:12的版本
2013年3月1日
-
计算问题与算法。
- 计算问题:input + output + their relationship。
- 算法:well-defined computational procedure for achieving an input-output relationship。
-
好算法。
- 要素:正确性、高效性、易实现性。
- 设计流程:思路-->过程-->正确性-->效率。
-
算法的正确性分析。
- partially correct:基于checkpoint和invariant。
- totally correct:partially correct + termination。
-
算法的效率分析。
- RAM的要素:数据类型、数据存储方式;指令类型、指令执行方式。
- running time的计算:cost*times;best/worst/average case。
-
算法效率的渐进表示法。
- Theta, O和Omega的含义:基于集合;基于极限。
- Theta vs. O:用O避免分情况讨论。
- O vs. o:基于集合;基于极限。
- 渐进表示法的比喻:大小关系;相似的性质,但无trichotomy。