How can I learn if an algorithm runs in O(n) time, or O(nlogn)?

This question already has an answer here:

Well here goes my first answer...

O() notation of an algorithm (though it could apply to any function) is somewhat like an upperbound on the algorithms growth rate. The case you are probably concerned with is the function that relates the number of operations your algorithm does for a given input size. You seem to be asking for a step by step approach so I'll attempt one:

Here's an example: Lets say List is an array of numbers and lSize is the number of items in the array.

for (int i=0; i < lSize; ++i){
  for (int j = i+1; j<=lSize; ++j){
    if (List[i] > List[j]){ //swap the elements
      int temp = List[i];
      List[i] = List[j];
      List[j] = temp;
    }
   }
}

Let's count the number operations required to sort a list of n items using the Selection Sort algorithm shown above.

Step 1

For a list size of n, how many operations does this algorithm require to sort (in terms of n)? Here lSize takes on the value of n. We have two for loops, one nested inside the other. The outer loop is easy, it executes once for every element in the List; or n times. Inside that loop is another for loop who's number of operations isn't immediately as obvious. This loops number of iterations depends on the current value of i in the outer for loop. If you sit down with some test values and write out the series that emerges you'll see that the inner loop first runs n times then (n-1) times then (n-2) times and so on, the total count described: n + (n-1) + (n-2) ... 2 + 1. You'll notice that this is the sum of all the numbers from 1 to n. If n = 100 then the number of total iterations of the inner loop would be 100 + 99 + 98 + 97 ... 2 + 1. This is an arithmetic series and can be simplified for n items to be: n*(n-1)/2. That is how many times the operations inside the inner loop get evaluated. Since there's 3 operations inside the inner loop that means the total number of operations for n items is 3 * n*(n-1)/2. Rewritten in a form easier for the next part, (3/2)n^2-(3/2)n.

Step 2

We now have our function. Where f() is the number of operations performed by our algorithm f(n) = (3/2)n^2-(3/2)n. Obviously, the fastest growing term is the (3/2)n^2 so we drop the (3/2)n. This leaves (3/2)n^2 for which we get rid of the (3/2) coefficient. This leaves n^2. Therefor, we can say f(n) is O(n^2).

This is basically the recipe for describing an algorithm in O() notation. This neglects the important whys and describes a brainless recipe for producing an answer. Why summarize algorithms this way? Why is ok to just forget about a term or coefficient? The answers to those questions are available in a more rigorous textbook description.

I hope I didn't make any terrible errors, it's a bit late.

Complexity depends on what your input is and which variables your algorithm uses to compute the output.

A few simple examples to help you understand basic algorithm complexity:

// This is O(n)
for (int i = 0; i < array.length; i++) {
  sum += array[i];
}

// This is O(n)
for (int i = 0; i < array.length / 2; i++) {
  sum += array[i];
}

// This is O(n)
for (int i = 0; i < array.length / 200; i++) {
  sum += array[i];
}

// This is O(1)
array[i]; // where i is an int

// This is O(1)
for (int i = 0; i < 10000; i++) {
  sum += array[i % array.length];
}

// O(n) that contain O(n) operation => O(n^2)
for (int i = 0; i < matrix.length; i++) {      
  for (int j = 0; j < matrix[i].length; j++) { // O(n)
    sum += matrix[i][j];
  }
}

There lots of famous algorithms to study to know how to compute algorithm complexity well. For O(log(n)) complexity for example, take a look at: http://en.wikipedia.org/wiki/Binary_search_algorithm

When it comes to evaluate real world algorithm, the complexity of some operation may be hidden in the representation you use to store your values. For example, in Java, you have ArrayList (a) and LinkedList (ll) which can used with the interface List (l). So the following line:

l.get(i); // where i is int and l is List.

may take O(1) time or O(n) time depending on the real structure of the list.

You can read this pages for more information: http://en.wikipedia.org/wiki/Analysis_of_algorithms http://en.wikipedia.org/wiki/Computational_complexity_theory Algorithm Complexity Time

In the first instance, you can learn this kind of thing by:

When you get enough experience, you can pick up some intuitive short-cuts for estimating the complexity of an algorithm.

One technique that some people suggest it to measure the performance over a range of values of the problem size variable (or variables), graphing them, and attempting to fit a curve. However, there are problems with this:

In short, this approach often doesn't give reliable answers.

上一篇: O循环的符号

下一篇: 如何在O（n）时间或O（nlogn）运行一个算法？