当前位置：文江博客话题详情

在哪里可以找到不同 STL 容器复杂性（性能）的比较？

发布于 2024-07-25 08:32:01 字数 135 浏览 4 评论 0原文

我在谷歌上搜索了很长一段时间，以便找到一个比较，以显示所有 STL 容器在插入/推擦除/弹出等方面的复杂性差异。我没有找到任何结果。我所有的 STL 书中也没有。有什么提示吗？

我当然知道一些经验法则。但定义在哪里呢？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

删除会话 2024-08-01 08:32:01

尝试使用

http://www.sgi.com/tech/stl/complexity.html< /a>

http://www.sgi.com/tech/stl/table_of_contents.html

来自complexity.html：

从根本上来说，很难
定义渐近的概念
算法复杂度精确为
真正的计算机硬件而不是
抽象机器模型。这样我们就解决了
遵循以下准则：
要使算法 A 的运行时间为 O(f(n))，必须有
对应的算法A'即
在机器上任意纠正
long 指针和 size_t 类型，例如
A 和 A' 基本上执行
相同的操作顺序
实际硬件。（在简单的情况下A
和A'将是相同的。其他
情况 A 可以简化为
地址的知识是
有界。）对于足够的输入
大尺寸 n，A' 最多必须取
时间 Cf(n)，其中 C 是常数，
与 n 和地址无关
尺寸。（指针、size_t 和 ptrdiff_t
操作被假定采取
独立于它们的恒定时间
尺寸。）
所有容器或迭代器复杂性规范均参考
摊销的复杂性。个人
操作可能需要更长的时间
指定的。但只要足够长
相同的操作顺序
容器或迭代器将采取
最多只要相应的总和
指定的运营成本。
算法指定最坏情况或平均情况
性能，并确定哪些性能。
除非另有说明，平均值
假设容器元素是
从有限类型中选择更多
可能的值比大小
容器，以及容器元素
是独立一致的
分布式。
操作 f 的复杂性规范假设操作
由 f 调用最多需要
指定的运行时间。但算法
如果
调用的操作只不过是
对数因子慢于
在预期情况下指定。
如果操作比函数 F 中假定的更昂贵
当前的STL，那么F将在以下位置减速
与增加的成本成正比。
任何未来未能完成的操作
满足这个属性将使
明确。
为了使其精确，假设指定 F 使用时间 f(m)
输入大小为m。 F 使用运算 Gk，
指定运行时间 gk(n) on
输入大小如果 F 用于
每个 Gk 较慢的上下文
最多比预期高一个因素
h(n)，则 F 最多减慢 a
因子 h(m)。这成立是因为没有
当前算法的应用
运算 Gk 到输入
明显大于 m。

Try with

http://www.sgi.com/tech/stl/complexity.html

http://www.sgi.com/tech/stl/table_of_contents.html

From complexity.html:

Fundamentally, it is difficult to
define the notion of asymptotic
algorithm complexity precisely for
real computer hardware instead of an
abstract machine model. Thus we settle
for the following guidelines:
For an algorithm A to have running time O(f(n)), there must be a
corresponding algorithm A' that is
correct on machines with arbitrarily
long pointer and size_t types, such
that A and A' perform essentially the
same sequence of operations on the
actual hardware. (In simple cases A
and A' will be the same. In other
cases A may have been simplified with
the knowledge that adresses are
bounded.) For inputs of sufficiently
large size n, A' must take at most
time Cf(n), where C is a constant,
independent of both n and the address
size. (Pointer, size_t, and ptrdiff_t
operations are presumed to take
constant time independent of their
size.)
All container or iterator complexity specifications refer to
amortized complexity. An individual
operation may take longer than
specified. But any sufficiently long
sequence of operations on the same
container or iterator will take at
most as long as the corresponding sum
of the specified operation costs.
Algorithms specify either worst-case or average case
performance, and identify which.
Unless otherwise stated, averages
assume that container elements are
chosen from a finite type with more
possible values than the size of the
container, and that container elements
are independently uniformly
distributed.
A complexity specification for an operation f assumes that operations
invoked by f require at most the
specified runtime. But algorithms
generally remain appropriate if the
invoked operations are no more than a
logarithmic factor slower than
specified in the expected case.
If operations are more expensive than assumed by a function F in the
current STL, then F will slow down at
most in proportion to the added cost.
Any future operations that fail to
satisfy this property will make that
explicit.
To make this precise, assume F is specified to use time f(m) for
input of size m. F uses operations Gk,
with specified running times gk(n) on
input size n. If F is used in a
context in which each Gk is slower
than expected by at most a factor
h(n), then F slows down by at most a
factor h(m). This holds because none
of the current algorithms ever apply
the operations Gk to inputs
significantly larger than m.