3

我正在尝试准备一个演示文稿，向我的同事解释算法分析的基础知识——他们中的一些人以前从未有过关于这个主题的讲座，但每个人都至少有几年的编程经验和良好的数学背景，所以我想我可以教这个。我可以很好地解释这些概念，但我需要一些导致因素的代码结构或模式的具体示例，以便我可以演示它们。

几何因素（n、n^2、n^3 等）很简单，嵌入循环使用相同的标记，但我迷失了如何描述和展示一些不太常见的因素。

我想在演示文稿中加入指数（2^n 或 c^n）、对数（n log(n) 或只是 log(n)）和因子（n！）因素。有哪些简短的、可教的方法可以在代码中获取这些内容？

4

4 回答 4

3

一个分而治之的算法，每次将问题一分为二，都会做一定的工作量O(log n)。例如二分查找。

一种分治算法，每次将问题分成两半时都会做线性工作O(n * log n)。例如合并排序。

通过分别迭代集合的所有子集或集合的所有排列，可能最好地说明指数和阶乘。

于 2012-09-12T17:04:31.730 回答
2

嗯！问题很简单。有许多 NP-完全 n! 旅行商问题等时间问题

于 2012-09-12T17:05:05.260 回答
2

指数：天真的斐波那契实现。

n log(n) 或只是 log(n)：排序和二进制搜索

Factorial：天真的旅行推销员解决方案。NP完全问题的许多幼稚解决方案。

于 2012-09-12T17:06:08.170 回答
0

毫无疑问，选择一种排序算法 - 每个人都知道他们应该做什么，因此它们很容易解释与复杂性相关的东西：维基百科有一个很好的概述

于 2012-09-12T17:09:09.217 回答