gpt4 book ai didi

algorithm - 如何模拟算法的执行时间?

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:12:54 25 4
gpt4 key购买 nike

算法运行时间有哪些模型?

我们都希望合并排序比冒泡排序更快,并注意到合并排序进行 O(n log n) 与冒泡排序的 O(n2) 比较。

对于其他算法,您计算其他操作(比较和交换除外),例如指针取消引用、数组查找、固定大小整数的算术等。

还有哪些其他方法可以对执行时间进行建模?

我自己知道的一个方法是计算从磁盘读取和写入磁盘的 block 数;查看我对 When does Big-O notation fail? 的回答以获得冗长的描述。

另一个是计算缓存未命中的次数。这通过查看内存层次结构的所有级别扩展了 I/O 模型。

第三,对于分布式算法(例如在安全的多方计算中)是计算通过网络传输的数据量(通常以通信轮数或消息数来衡量)。

为了预测算法的性能,还有哪些其他有趣的东西可以计算(而不是计算!)?

此外,这些模型有多好?据我所知,对于磁盘上的数据,缓存不经意的算法与 I/O 高效算法相比具有竞争力,但对于内存中的算法则不然.

特别是:这些模型在哪些特定情况下会错误预测相对性能?根据我自己的实验,当数据小到足以放入内存时,Fibonacci 堆不会加速 Dijstra 的最短路径(相对于二进制堆)。

最佳答案

您必须定义一个计算模型,估算每个操作的成本,然后根据这些成本分析您的算法;当然,成本取决于具体的环境和你要部署算法的底层机器的特性,所以这个问题太笼统了。

在算法类(class)中,我们只是假设每次操作的成本为1,所以我们只是计算循环了多少次;在使用主内存的算法中,我们假设每个操作,除了读/写和 I/O 之外,成本为 0(读/写为 1),依此类推。

这些模型是否与现实紧密相关?这取决于实际情况:您的环境和机器。

您的缓存未命中计算在核心双核上可能是正确的,但在单元处理器上是错误的,例如,您必须手动传输 SPE 内存的内容。

关于algorithm - 如何模拟算法的执行时间?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/947525/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com