APCompSci-Fall/Notes1211.txt at master · tyleri/APCompSci-Fall · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
Aim: How can we analyze algorithm efficiency?

Do Now: what are some ways you could measure how
		efficient an algorithm is? Are there any
		possible issues with these measures?


Efficiency
	Algorithm efficiency cafn refer to space
	efficiency or time efficiency. Often the two
	are inversely related (but not always).

	When discussing efficiency, it's important to
	be aware of the difference between the
	efficiency of an algorithm vs the power of the
	computer on which is it being run.


	Big-O Notation
		Used to formalize the analysis of algorithms.

		Provides an estimated upper bound for the
		amount of "work" done. It is not an exact
		measure.

		Refers to the efficiency of an algorithm
		as the amount of data (n) increases.

		Example:
			for (int i=0; i < a.length; i++)
				a[i] = a[i] * 10;

			Big-O value of this loop?
				The loop increases at the same
				rate as n:
					O(n)

			for (int i=0; i < a.length; i++)
				for (int j=0; j < a.length; j++)
					a[j] = a[j] + i;

			Big-O value of this loop?
				Every single increase in n results
				in n more passes:
					O(n * n) = O(n^2)

			for (int i=0; i < a.length; i++)
				a[i] = i;
			for (int j=0; j < a.length; j++)
				a[j] = a[j] + 10;