Analysis of Algorithms - Gordon College

Analysis of Algorithms - Gordon College

Analysis of Algorithms CPS212 Gordon College Measuring the efficiency of algorithms There are 2 algorithms: algo1 and algo2 that produce the same results. How do you choose which algorithm to keep.

Algorithm Efficiency Measuring the efficiency of algorithms How do you determine an algorithms inherent efficiency? Code them up and compare their running times on a lab machine.

How were they coded? We want to compare the algorithms - not their implementations What computer do we use? What else is running? What data is a fair test of an algorithms efficiency. Measuring the efficiency of algorithms Goal: Solution:

Measure the efficiency of an algorithm independent of implementation, hardware, or data. Analyze and represent the number of operations the algorithm will perform as a function of input. Example: Copying an array with n elements requires x operations. What is x? Growth rates

Algo1 requires n2 / 2 operations to solve a problem with input size n Algo2 requires 5n + 10 operations Which is the better algorithm for the job? Order of magnitude growth analysis A function f(x) is O(g(x)) if and only if there exist 2 positive constants, c and n, such that | f(x) | cg(x) for all x > n cg(x) f(x)

number of operations size of input set Order of magnitude growth analysis Asymptotic growth - as the growth approaches infinity An asymptote of a real-valued function y = f(x) is a curve which describes the behavior of f as either x or y tends to infinity. cg(x)

f(x) number of operations size of input set Order of magnitude growth analysis Important points:

Focus only on the growth Shape of g(x) is essential As the input set grows large (ignore the shape for small x) cg(x) f(x) number of operations size of input set Standard function shapes: constant O(1)

Examples? f(x) = cg(x) number of operations size of input set Standard function shapes: linear O(x)

Examples? cg(x) f(x)=ax+b number of operations size of input set Standard function shapes: logarithmic O(log x) (base 2)

QuickTime and a decompressor are needed to see this picture. bc = a 23 = 8 logba = c log28 = 3 log(x*y) = log x + log y log(xa) = a log x Examples?

Standard function shapes: Polynomial O(x2) Examples? Polynomial vs. Linear Polynomial vs. Linear Example: 50n + 20 & n2

4000 3500 At what point will n2 surpass 50n+20? 3000 n2 2500 2000 = 50n+20 Solve for xquadratic formula 1500

1000 500 0 0 10 20 30 n2 40 50

60 70 - 50n - 20 = 0 n = 101/2 = 50.5 n = -1/2 Standard function shapes: Exponential O(cx) Examples? Hamiltonian Circuit Traveling Salesman

Optimization problems Solution: Limit to small input sets Isolate special cases Find approximate solution (near optimal) Complexity in action QuickTime and a decompressor are needed to see this picture. Real Examples

Searching (sequential) Unit of work: comparisons Best case: O(1) [theta] Worst case: O(n) [theta] Average Case: O(n) [theta] Real Examples Sort (selection)

Unit of work: comparisons and exchanges Best case: O(n2) [theta] Worst case: O(n2) [theta] Average Case: O(n2) [theta] Real Examples Search (binary)

Unit of work: comparisons Best case: O(1) [theta] Worst case: O(log n) [theta] Average Case: O(log n) [theta]

Recently Viewed Presentations

  • Floating Point Hardware and Algorithms

    Floating Point Hardware and Algorithms

    Floating Point Hardware and Algorithms * CH.3 * Review * * Adder gate level diagram Adder Verilog module Processing Verilog files using Icarus Verilog Simulation verilog module definition using vvp Floating point representation Adder Circuit * * Adder (a,b,cin) s,...
  • The Rise of Absolute Monarchy (1550-1800)

    The Rise of Absolute Monarchy (1550-1800)

    Complete the Absolute ruler organizer using the Jarrett Book p. 201-203. Put as much information as you can. You may use online research but please be accurate. Please turn in for a grade. Absolute Ruler Organizer
  • Lecture 5 - Computer Science & E

    Lecture 5 - Computer Science & E

    Lecture 6 Shell Part II: sh, bash, ksh Parsing and Quoting How the Shell Parses Part 1: Read the command: Read one or more lines a needed Separate into tokens using space/tabs Form commands based on token types Part 2:...
  • Acquisition Valuation - New York University

    Acquisition Valuation - New York University

    Tax Benefits: The tax paid by two firms combined together may be lower than the taxes paid by them as individual firms. Debt Capacity: By combining two firms, each of which has little or no capacity to carry debt, it...
  • Essential Question: How does the position of the sun, earth ...

    Essential Question: How does the position of the sun, earth ...

    Essential Question:How does the position of the sun, earth, and moon affect each other? S6E2a. Demonstrate the phases of the moon by showing the alignment of the earth, moon, and sun. S6E2b. Explain the alignment of the earth, moon, and...
  • The State as a Model Litigant: Recent Analyses

    The State as a Model Litigant: Recent Analyses

    Ian Freckelton SC [email protected] ... Dale Boucher "An Ethical Code… Not a Code of Conduct" (1996) 79 Canberra Bulletin of Public Administration 3 at 4. The meaning of [model litigant] is sometimes expressed as being firm but fair. Sometimes, too,...
  • NATIONAL STEM CONSORTIUM Kim Law Cyber Technology Team

    NATIONAL STEM CONSORTIUM Kim Law Cyber Technology Team

    Technical courses were developed by experience faculty from multiple colleges in collaboration with industry leaders. The STEM readiness course was developed by faculty from all 10 partner colleges and industry partners - more on this when we talk about the...
  • MOSFET - Universitas Udayana

    MOSFET - Universitas Udayana

    * * * * * * * * * Harga ID tergantung dari harga Vt, COX, dan W/L yang sangat bervariasi pada divais yang mempunya nomor/ jenis yang sama. Vt dan μn tergantung pada suhu. Jadi kalau kita menetapkan harga...