Why do O(n^2) algorithms become more inefficient the larger the amount of items it has to sort?_问答_开发者

could anyone give a clear definition as to WHY O(n^2) algorithms become more and more inefficient th开发者_如何学编程e bigger the amount of items they have to sort?

E.g. A bubble sort - 4096 items takes 24.56 ms to sort where as 8192 items take 98.56ms to sort. Could anyone clearly explain why the growth is so?

that's the meaning of being a O(n^2) function.

that for n items your algoritm will take somewhat like O(n^2).

(8192^2)/(4096^2)=4 that is 2^2 of growth

and 98.56/24.56=4.013..

Strictly speaking, Big-O doesn't tell you about the growth for numbers you actually use.

Big-O notation is about what happens in the limit as the size of the problem (n) tends to infinity. Specific small numbers like 4096 and 8192 are irrelevant to big-O classification. Furthermore, big-O is an upper limit. Bubble sort is O(n^2). It is also O(n^3), and O(n^27), and O(2^n), because all of those functions also provide upper bounds on its running time in the limit. Very loose upper bounds, but bounds nonetheless.

In practice, many or most algorithms that you'll use, can be observed for realistic values of n, to follow a trend corresponding to their "best" big-O complexity. And that's what you're seeing here - doubling the size quadruples the time, because time is approximately proportional to n^2. Because time is proportional to n^2, the algorithm is O(n^2). The reverse implication does not necessarily hold.

People commonly say "bubble sort is O(n^2)", and they mean, "the time taken to bubble sort is proportional to the square of the input size, ignoring a small percentage of special cases which are much faster (already-sorted data in the case of bubble sort)". Both statements are true, but the latter is not what the former actually means, so occasionally it's confusing. Several answers here say the same thing, and they're wrong too as far as the mathematical definition of big-O is concerned. But the incorrect usage is so common that it can't be ignored, presumably because people are informally introduced to big-O classifications of algorithms without ever being taught a formal definition.

So, when someone tells you that an algorithm is O(n^2), there's a fairly high probability that what they're trying to tell you is that its worst case is Θ(n^2), and if so they might well be further trying to tell you that this trend is observable for the kinds of n you care about. Given this abuse of notation, that's why "O(n^2) algorithms" all become less efficient as you increase n.

O(n²) means, among many other things, that the ratio between the time required to sort X elements and that required to sort Y elements is approximately X²/Y² (becoming closer to that as X and Y approach infinity).

Let's calculate:

8192² / 4096² = 2² = 4.00
98.56 / 24.56      ≈ 4.01

Indeed, your sort is O(n²), and that's what you should expect.

O means that upper bound, that is the growth of the function will not exceed the growth of the function which is defined inside the O (). f(x) = O (g(x)) means |f(x)| <= C|g(x)| for some x > k and for some constant C (which are called the witnesses). Means that for some C and k , if we plot the functions then for all points x > k g(x) would be always greater for every x > k, ie the g(x) defines an upper bound. Note that the function g(x) can have lower values than f(x) for x<k.

This can be thought as a car travelling with 40kmph at constant speed, and another car travelling from 0 kmph but has some finite acceleration. The first car does not have any growth but because the second car has growth greater than the first car, we can tell that at some point of time the second car would have velocity more than that of the first car.

As shevski and others have said, an O(n2) algorithm has by definition that behaviour. A bubble sort is only handy if you really think your data is already sorted (the complexity degrades to O(n)), which means approximately that each element is looped through and nothing is done.

I would advice you to look at Wikipedia and read about Big O notation and Sorting algorithms; the articles are really readable.

As for the notation itself, O(n2) can be faster than a O(n logn) algorithm for certain data sets and sizes, it depends on the constants. And even if not faster, memory consumption can be a factor in sorting huge data sets.

As always, the best sorting algorithm depends on the data and the constraints of the hardware (memory). Although I dare say that bubblesort is hardly ever the way to go.

If you're more into animations, have a look here where you can see how various sorting algorithms work.

If an algorithm has running time O(n²), you can intuitively think of it as meaning that if you increase n by some factor k, the run time will increase by a factor of k².

This means that if you double the size of the input, the algorithm will take roughly 4 times longer to run. This is consistent with the timings you're experiencing.

There have been a lot of great answers to the theory behind Big O and sorting, but i suspect thats not your concern.

The reason why some algorithm (most actually) gets more infective with larger datasets is in short, because every added element, must be considered along with rest of the data.

If you take bubble sort: If you add an element to the end of the list and sort it, you might have to run through the entire list. This of course takes longer with a long list. Therefore the algorithm is less efficient per element, the more elements you add.

An other O(n^2) example: Say you have n points, and for each one you must find its nearest neighbor. If n=10, you will have to do 9 comparisons for each point => 9*10=90 comparisons. If you double the size, n=20, you will have to do 19 comparisons pr. point. Therefore the algorithm becomes "less efficient" for each point. => 19*20 = 380 comparisons approx 2^2=4 times a many.

It all depends on data. For bubble sort O(n^2) is worst-case scenario. It can be as good as O(n) if you are sorting already sorted list.

Generaly O() means worst-case scenario for given algorithm.

For bubble sort you just need to look at an implementation and count how many comparisons there are. Then I think you'll understand.