How to determine the complexity of an algorithm fu

问题:

How do you know if a algorithm function takes linear/constant/logarithmic time for a specific operation? does it depend on the cpu cycles?

回答1:

There are three ways you can do it (at least).

1. Look up the algorithm on the net and see what it says about its time complexity.

2. Examine the algorithm yourself to look at things like nested loops and recursion conditions, and how often each loop is run or each recursion is done, based on the input size. An extension of this is a rigorous mathematical analysis.

3. Experiment. Vary the input variable and see how long it takes depending on that. Calculate an equation that gives you said runtime based on the variable (simultaneous equation solving is one possibility here for O(n^c)-type functions.

Of these, probably the first is the easiest for the layman since it will almost certainly have been produced by someone more knowledgable doing the second :-)

回答2:

At first the function may take any time to execute the algorithm. It can be quite non-linear also and even infinite.

Shortly if you have an algorithm then it is used the abstraction called Turing machine. It is used to measure a number of operations required to perform the algorithm before it halts.

More precise info you may get here WIKI::Computational complexity theory

回答3:

About dependency on CPU: The answer is NO - time complexity is totally cpu independent. This is because complexity shows - How algorithm's demands on cpu resources increases with increasing algorithm input data size. In other words it is a function. And functions are the same everywhere - be it on different machines or on different planet :)