Big O对运行时间的粗略估计 [英] Rough estimate of running time from Big O

问题描述

如果程序的时间复杂度为 O（n ^ 2），如何用项表示
运行时间

我需要一个粗略的估算值，以了解是否需要优化，或者我可以
继续执行我的代码。...时间限制为0.6秒

问题不在于时间复杂度的计算...而是从时间估算运行时间复杂性

解决方案

无法根据其Big-O等级来计算或估算某些代码的运行时间。

Big-O告诉您方法如何根据执行的操作进行缩放。不知道一个操作要花多长时间。另外，CPU在并行执行某些操作时可能会好坏，这会使其变得更加困难。

仅 的计算方法如果您有性能瓶颈，请执行以下操作：

1. 观察代码运行。这会花费太长时间吗？


2. 测量代码的运行情况。这会花费太长时间吗？


3. 缩小测量范围，直到您知道代码的哪一部分是主要瓶颈。


4. 确定是否可以更改后，您会从中得到什么吗？

如果您还知道该代码的Big-O等级，例如，如果您将要处理的项目数量增加一倍，则可以用它来确定瓶颈是否会成倍恶化。

If the time complexity of my program is,say O(n^2),How do I express running time in terms of seconds for a large value of n,10^6 ?

I need a rough estimate of that to know if optimization is required or I can proceed with my code....Time Limit is 0.6 seconds

The question is not about calculation of Time complexity....It's about estimation of running time from Time complexity

解决方案

There is no way to calculate or estimate the running time of a some piece of code based on its Big-O rating.

Big-O tells you how a method scales in terms of operations to perform. It has no idea how long one operation take to execute. Additionally, CPUs may be good or bad at executing some of the operations in parallel which makes it even harder.

The only way to figure out if you have a performance bottleneck is to do the following:

1. Observe the code running. Does it take too long?
2. Measure the code running. Does it take too long?
3. Narrow down the measurements until you know which part of the code is the main bottleneck.
4. Decide if it can be changed, will you get out of it what you put into it?

If you also know the Big-O rating of that code you can use that to decide if the bottleneck is going to be exponentially worse if you, as an example, double the number of items to process.

这篇关于Big O对运行时间的粗略估计的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！