淺談設(shè)計(jì)獲勝策略-在線瀏覽
2024-08-05 11:58本頁面
【正文】 is: When do you spend more time debugging a program, and when do you cut your losses and move on?. Consider these issues: How long have you spent debugging it already? What type of bug do you seem to have? Is your algorithm wrong? Do you data structures need to be changed? Do you have any clue about what39。 but you might be able to solve another from scratch in 45 mins. When do you go back to a problem you39。 Tricks Brute force it when you can KISS: Simple is smart! Hint: focus on limits (specified in problem statement) Waste memory when it makes your life easier (if you can get away with it) Don39。t reuse variables, stepwise refinement, COMMENT BEFORE CODE. Avoid pointers if you can Avoid dynamic memory like the plague: statically allocate everything. Try not to use floating point。 /* increase the value of i by */ is worse than useless Explain code trickery Delimit amp。 use this to rewrite and improve your game plan! Complexity Basics and order notation The fundamental basis of plexity analysis revolves around the notion of ``big oh39。 notation, for instance: O(N). This means that the algorithm39。 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
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1