曲径通幽论坛

 找回密码
 立即注册
搜索
查看: 4002|回复: 0

固定时间与线性时间复杂度

[复制链接]

716

主题

734

帖子

2946

积分

超级版主

Rank: 9Rank: 9Rank: 9

积分
2946
发表于 2014-1-15 12:07:48 | 显示全部楼层 |阅读模式
假设一个长盒子里一字排开装满了包裹,现在这个盒子只有一端是打开的。现在从打开的这端取出一个包裹,那么这是一个固定时间的任务;不管盒子里装有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。固定复杂度意味着操作发生在运行阶段,但独立于对象中的元素数目。线性复杂度意味着时间与元素数目成正比。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|曲径通幽 ( 琼ICP备11001422号-1|公安备案:46900502000207 )

GMT+8, 2024-3-29 06:38 , Processed in 0.081242 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表