我正在尝试准备一个演示文稿,向我的同事解释算法分析的基础知识 - 他们中的一些人以前从未听过关于该主题的讲座,但每个人都至少有几年的编程经验和良好的数学背景,所以我想我可以教这个。我可以很好地解释这些概念,但我需要一些代码结构或模式的具体示例,这些代码结构或模式会导致因素,以便我可以证明它们。
几何因子(n、n^2、n^3 等)很简单,使用相同标记的嵌入式循环,但我不知道如何描述和展示一些不太常见的因子。
我想合并指数(2^n 或 c^n)、对数(n log(n) 或只是 log(n))和 factoral (n!) 演示文稿中的因素。在代码中获取这些内容的一些简短的、可教授的方法是什么?
最佳答案
每次将问题分成两半时,分而治之算法的工作量是恒定的,O(log n)
。例如二分查找。
每次将问题分成两半时,分而治之算法的工作量是线性的,O(n * log n)
。例如归并排序。
指数和阶乘可能最好通过分别迭代一个集合的所有子集或一个集合的所有排列来说明。
关于algorithm - 你如何在代码中获取各种算法分析因素?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12393035/