Finding/Calculating complexity of a method
Possible Duplicate:
Big O, how do you calculate/approximate it?
Plain English explanation of Big O
I just saw this question: Find nearest number in unordered array. In answers peoples are talking about complexity of approach they are proposing. How do they calculate it? What does O(n) or O(logn) means? How to find/Calculate complexity of a method/program?
Complexity has sense when your algorithm works with n similar elements. And says, how the time changes according to changes of n. So, if n rises 2 times and the time raises 2 times, you have O(n) complexity.
If the time raises as (n^2+2000n) function, we also say that the complexity is again O(n^2). The theory thinks only on greater values of n, greater than any other constants in your algorithm. So, the theory does not always fits your need, beware that. It is not the problem of the theory of algorithms, it is problem of its application that often doesn't pay attention to the important details
How you can guess? Well, if you are doing the same operation n times, where n is the number of array elements, you have O(n). If you are doing the same operation first n times, than n-1 times, than n-2 and down to 1, you have complexity n+(n-1)+...+1. It is n(n+1)/2, that is again const*n+const2*n^2. So, it is O(n^2). When n will be large enough, twice n will mean 4 time the time. Logics and arithmetics.
Short answer: O(), o(), etc... are notations describing the trend at which a function will grow, depending of its variables. eg f(x) = x^2 + x - 6 => O(x^2) because the growth is driven by the highest polynomial degree in the function. More on this specific topic: Big O notation
Long answer: those notations are the very basis of the study of algorithms and computation theory. you might want to read a nice book about it. One of the most famous books on Algorithms out there
Also, OpenMIT has the whole course available for free. It's very interesting!.
That is known and Big O Notation and is used to find the Computational Time Complexity of a given algorithm. You can find a short guide on how to calculate it for yourself here. Although it is not Java, the concept of what time complexity is, is language agnostic so you should be fine. However note that method with similar names can have different time complexities accross different languages.
链接地址: http://www.djcxy.com/p/39352.html上一篇: 这些相关嵌套循环的时间复杂度是多少？
下一篇: 查找/计算方法的复杂性