淺談設(shè)計(jì)獲勝策略-wenkub.com
2025-06-22 11:58 本頁面
【正文】 here we will concentrate discussion on time. One deduces the O( ) run time of a program by examining its loops. The most nested (and hence slowest) loop dominates the run time and is the only one mentioned when discussing O( ) notation. A program with a single loop and a nested loop (presumably loops that execute N times each) is O(N 2), even though there is also a O(N) loop present. Of course, recursion also counts as a loop and recursive programs can have orders like O(b N), O(N!), or even O(N N). Rules of thumb When analyzing an algorithm to figure out how long it might run for a given dataset, the first rule of thumb is: modern (1999) puters can deal with 10M actions per second. In a five second time limit program, about 50M actions can be handled. Really well optimized programs might be able to double or even quadruple that number. Challenging algorithms might only be able to handle half that much. 640K is a really tight memory constraint. Happily, the 19992000 season is the last time this constraint applies. 210 ~approx~ 10 3 If you have k nested loops running about N iterations each, the program has O(N k) plexity. If your program is recursive with b recursive calls per level and has l levels, the program O(b l) plexity. Bear in mind that there are N! permutations and 2 n subsets or binations of N elements when dealing with those kinds of algorithms. The best times for sorting N elements are O(N log N). DO THE MATH! Plug in the numbers. Examples A single loop with N iterations is O(N): 1 sum=0 2 fori=1ton 3 sum=sum+i A double nested loop is often O(N 2): fill array a with N elements 1 fori=1ton1 2 forj=i+1ton 3 if(a[i]a[j]) swap(a[i],a[j]) Note that even though this loop executes N x (N+1) / 2 iterations of the if statement, it is O(N 2) since doubling N quadruples the execution times. Solution Paradigms Generating vs. Filtering Programs that generate lots of possible answers and then choose the ones that are correct (imagine an 8queen solver) are filters. Those that hone in exactly on the correct answer without any false starts are generators. Generally, filters are easier (faster) to code and run slower. Do the math to see if a filter is good enough or if you need to try and create a generator. Preputation Sometimes it is helpful to generate tables or other data structures that enable the fastest possible lookup of a result. This is called preputation (in which one trades space for time). One might either pile preputed data into a program, calculate it when the program starts, or just remember results as you pute them. A program that must translate letters from upper to lower case when they are in upper case can do a very fast table lookup that requires no conditionals, for example. Contest problems of
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號-1