程式規格、設計、與分析

**<1> Time analysis:**

**<2> Big-O notation: the order of algorithm.**

- an algorithm is said th be O(
*N*)^{p}

if its operation count Q satifies:where C is a constant. if p=1 the algorithm is called linear.

if p=2 the algorithm is called quadratic. - An algotithm s called logarithnic O(log
*n*)

if its operation count Q satifies:

ex. count 2n 4n n 2n 4n n ^{2}4n ^{2}16n ^{2}log n log n + log 2 log n + log16 Remark:

- The order of an algorithm generally is more important than the speed of the processor.

ex.n O(n) / 3n O(n ^{2}) / n^{2}+2nO(log n) / log n + 1 10 30 120 2 1000 300 10200 3 10000 3000 1002000 4 - A loop that does a fixed amount of operations n times requires O(n) time.

eg.for ( i = 0 ; i < n ; i++ ) j = j + 1 ;

- worst-case, average-case, best-case analysis.
worst case Count the number of operations in average case bestt case

- The order of an algorithm generally is more important than the speed of the processor.