Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
2.0k views
in Technique[技术] by (71.8m points)

algorithm - Rough estimate of running time from 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

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

2.1m questions

2.1m answers

60 comments

57.0k users

...