曲径通幽论坛

标题: 固定时间与线性时间复杂度 [打印本页]

作者: easy 时间: 2014-1-15 12:07
标题: 固定时间与线性时间复杂度
假设一个长盒子里一字排开装满了包裹，现在这个盒子只有一端是打开的。现在从打开的这端取出一个包裹，那么这是一个固定时间的任务；不管盒子里装有10个还是100个，对于只取出 1 个包裹来说，时间都一样。

现在仍假设盒子是一端开口，现在任务是取出没开口那端的的包裹，则将是一项线性时间任务。如果盒子里有 10 个包裹，那么要取 10 次才能拿到该包裹；如果盒子里有 100 个包裹，那么就要取 100 次。

现在仍假设盒子是一端开口，且假设任务是取出任意一个包裹。对此，通常需要移动若干包裹才能取出你想要的包裹。在这种情况下，必须移动的包裹数目仍旧与容器中的包裹的数目成正比，所以这种任务仍然是线性时间复杂度。

假设，所有的包裹并不是放在一次排开的盒子里，而是平摊在其中，且可从任意方向将其取出，那么这种任务的复杂度将是固定时间的，因为可以直接取出想要的包裹，而不用移动其它的包裹。

假设“复杂度”可以表示为执行某些操作所需的时间。

1. 假设 X 表示容器类型，u 表示类型为 X 的标识符，比如 X 表示 vector<int>，那么 u 就是一个 vector<int> 对象。X u; 表示创建了一个名为 u 的空容器；X(); 表示创建了一个匿名的空容器。创建这两种容器的时间是固定的，因此该创建操作的复杂度为“固定”。

2. 假设 a 表示类型为 X 的值，那么执行 X u(a); （调用复制构造函数后，u == a）, 这个操作的复杂度是“线性”的，因为需要复制构造的内容越多，所耗费的时间也就越多。

3. 假设 T 表示存储在容器中的对象类型；如果只是确定或返回某个类型，如 X::iterator; （指向 T 的迭代器类型），又如 X::value_type; （返回 T 这个类型），像这样的表达式，其复杂度为“编译时间”，即时间在编译阶段就能确定下来。

上述几个复杂度，从快到慢依次为：编译时间，固定时间，线性时间。

如果复杂度为编译时间，那么操作在编译时执行，执行时间为 0。固定复杂度意味着操作发生在运行阶段，但独立于对象中的元素数目。线性复杂度意味着时间与元素数目成正比。

欢迎光临曲径通幽论坛 (http://www.groad.net/bbs/)