The ability to analyze a piece of code or an algorithm and understand its efficiency is vital for understanding computer science.
One approach to determining an algorithm's order is to start out assuming an order of O(1), an algorithm that doesn't do anything and immediately terminates no matter what the input. Then, find the section of code that you expect to have the highest order. From there, work out the algorithmic efficiency from the outside in -- figure out the efficiency of the outer loop or recursive portion of the code, then find the efficiency of the inner code; the total efficiency is the efficiency of each layer of code multiplied together.
For instance, to compute the efficiency of a simple selection sort
for(int x=0; x<n; x++)
{
int min = x;
for(int y=x; y<n; y++)
{
if(array[y]<array[min])
min=y;
}
int temp = array[x];
array[x] = array[min];
array[min] = temp;
}
We compute that the order of the outer loop (for(int x = 0; ..)) is O(n); then, we compute that the order of the inner loop is roughly O(n). Note that even though its efficiency varies based on the value of x, the average efficiency is n/2, and we ignore the constant, so it's O(n). After multiplying together the order of the outer and the inner loop, we have O(n^2).
In order to use this approach effectively, you have to be able to deduce the order of the various steps of the algorithm. And you won't always have a piece of code to look at; sometimes you may want to just discuss a concept and determine its order. Some efficiencies are more important than others in computer science, and on the next page, you'll see a list of the most important and useful orders of efficiency, along with examples of algorithms having that efficiency.
分享到:
相关推荐
Data scientists have to manage and maintain increasingly complex data projects, and with the rise of big data comes an increasing demand for computational and algorithmic efficiency. Large Scale ...
Data scientists have to manage and maintain increasingly complex data projects, and with the rise of big data comes an increasing demand for computational and algorithmic efficiency. Large Scale ...
9 Efficiency and ADTs 10 Linear Structures 11 Symbol Tables PART FOUR Recursive Lists 12 Recursive Lists 13 Trees 14 Expression Trees 15 Sets 16 Graphs 17 Looking Ahead to Java index
Data scientists have to manage and maintain increasingly complex data projects, and with the rise of big data comes an increasing demand for computational and algorithmic efficiency. Large Scale ...
Leverage agile principles to maximize development efficiency in production projects Learn from practical Python code examples and visualizations that bring essential algorithmic concepts to life Start...
Creating robust software requires the use of efficient algorithms, but programmers seldom think about them until a problem occurs....Learn advanced data structures to improve the efficiency of algorithms
Creating robust software requires the use of efficient algorithms, but programmers seldom think about them until a problem occurs....Learn advanced data structures to improve the efficiency of algorithms
Covers ‘hot’ topics, such as Software Defined Networking and energy efficiency, algorithmic advancements and techniques, especially in the area of impairment-aware routing and wavelength assignment...
Algorithmic Expression of a Hardware System Chapter 8. Using Computers to Solve Problems Part 3 Software Tools Supporting Program Execution Chapter 9. Computer Process Manipulation by Programs ...
algorithmic tool Meet the common data processing needs of C, Java and python programmers in daily programming, and effectively improve work efficiency. Based on reliable algorithm suite, support ...
2.5 Reasoning About Efficiency 2.6 Logarithms and Their Applications 2.7 Properties of Logarithms 2.8 War Story: Mystery of the Pyramids 2.9 Advanced Analysis (*) 2.10 Exercises 3 Data ...
Core™2 processor family (Penryn) and improve the performance and energy efficiency of a broad range of applications. This white paper describes how video encoders can utilize Intel SSE4 instructions ...
我证明如果市场有效,这意味着当前价格完全反映了过去价格中的所有可用信息,则P = NP,这意味着可以在多项式时间内验证其解决方案的每个计算问题也可以在多项式时间内解决。 通过展示我们如何“编程”市场以解决NP...