提问人：Software Guy 提问时间：9/24/2023 更新时间：9/24/2023 访问量：37
如何找到具有 O（n log n） 时间复杂度的输入大小的单位运行时间变化？[已结束]
How can I find the change in runtime per unit change in the size of input with an O(n log n) time complexity? [closed]
问：
如果一个程序的运行时间是 4.956 秒，输入大小为 10,000,000，如果我将输入的大小增加到 20,000,000，并且时间复杂度为 O（n log n）（近似运行时），运行时间会是多少？
答：
2赞
chqrlie
9/24/2023
#1
假设启动时间可以忽略不计，则该比率应约为
（2n.log（2n））/（n.log（n））
这简化为
（2.（log（n） + log（2）））/log（n）
2.（1 + log（2）/log（n））
因此，从 1000 万到 2000 万，该比率略高于 2，约为 2.086，运行时间约为 10.34 秒。
但请注意，除了算法时间复杂度之外，其他因素可能会显著影响运行时间，例如 CPU 缓存大小和内存过量，因此观察到的大样本量时间可能不遵循预期曲线。
评论
0赞
chqrlie
9/24/2023
@teapot418：感谢您的仔细检查，心算错误:)
评论