NZ NCEA Level 3 Digital Technologies
41 ملاحظات للمذاكرة لمادة NZQA NCEA Level 3 Digital Technologies، أعدّها cookie، في 7 أقسام تتبع موضوعات المنهج.
Notes for NZQA NCEA Level 3 Digital Technologies and Hangarau Matihiko, in a folder for each area of computer science the course analyses (complexity and tractability, computer graphics, computer vision, big data, formal languages and network communication protocols), with one note per topic, and a last folder on developing and reflecting on a digital outcome. Follows achievement standard AS91908 as registered for 2027. Delete the folders for the areas you are not studying.
ما المحتوى؟
الملاحظة الأولى
Complexity and tractability / Measuring algorithm efficiency and Big O
Why running time is not the measure
Timing a program with a stopwatch says as much about the computer as about the algorithm. A slow algorithm on a fast machine can beat a fast algorithm on a slow one, and the result changes with the language, the compiler, what else is running and the particular input. Computer scientists therefore measure an algorithm by how the amount of work it does grows as the input grows. The input size is written n: the number of items in a list, the number of cities in a route, the number of digits in a number.
Work is counted in basic steps, such as a comparison, an assignment or an arithmetic operation, each treated as taking one unit of time. The count is a function of n, and what matters is the shape of that function for large n. This is time complexity. Space complexity is the same idea applied to memory: how much extra storage the algorithm needs as n grows, not counting the input itself.
Counting steps
Consider a function that finds the largest value in a list of n numbers.
def largest(items):
best = items[0]
for x in items[1:]:
if x > best:
best = x
return bestThe loop runs n−1 times and each pass does one comparison and possibly one assignment. The total is roughly 2n steps at most, plus a constant for the set-up. Doubling the list doubles the work. Whether the exact figure is 2n or 3n+5 does not change that, which is why the constants are dropped.
Now a function that checks whether any two numbers in a list are equal by comparing every pair.
def has_duplicate(items):
n = len(items)
for i in range(n):
for j in range(i + 1, n):
if items[i] == items[j]:
return True
return FalseThe inner loop runs n−1 times for i=0, then n−2, and so on down to zero. The number of comparisons in the worst case is
For n=10 this is 45 comparisons, for n=100 it is 4,950 and for n=1,000 it is 499,500. Multiplying n by ten multiplies the work by about a hundred, which is the signature of work proportional to n2.
Big O notation
Big O notation describes an upper bound on how fast the number of steps grows. Writing f(n)=O(g(n)) means that for large enough n, f(n) is no bigger than some constant multiple of g(n). In practice two simplifications give the answer.
- Drop constant factors. 3n and 50n are both O(n).
- Keep only the term that grows fastest. n2+5n+100 is O(n2), because for large n the n2 term swamps the others.
So the duplicate check above is O(n2) and the largest-value function is O(n). Big O says nothing about small inputs: 100n is O(n) and n2 is O(n2), yet n2 is the smaller of the two until n passes 100. Big O is a statement about what happens as the input grows without limit.
Base of a logarithm does not matter inside Big O, because changing base multiplies by a constant. O(log2n) and O(log10n) are the same class and are written O(logn).
Common growth rates
| Notation | Name | Typical source | Example |
|---|---|---|---|
| O(1) | constant | one step regardless of size | reading items[i] from an array |
| O(logn) | logarithmic | halving the problem each step | binary search in a sorted array |
| O(n) | linear | one pass over the data | linear search, finding the maximum |
| O(nlogn) | linearithmic | divide, then merge linearly | merge sort |
| O(n2) | quadratic | two nested loops over the data | comparing every pair, bubble sort |
| O(n3) | cubic | three nested loops | naive multiplication of two n×n matrices |
| O(2n) | exponential | trying every subset | checking every subset of n items |
| O(n!) | factorial | trying every ordering | checking every route through n cities |
The table is in order of increasing growth. The jump from polynomial rates (n, n2, n3) to exponential and factorial rates is the dividing line the rest of this topic is built on.
How fast the rates grow
The table below shows the number of steps for a few sizes, assuming one step per unit.
| n | log2n | n | nlog2n | n2 | 2n |
|---|---|---|---|---|---|
| 10 | 3.3 | 10 | 33 | 100 | 1,024 |
| 20 | 4.3 | 20 | 86 | 400 | 1,048,576 |
| 30 | 4.9 | 30 | 147 | 900 | 1,073,741,824 |
| 100 | 6.6 | 100 | 664 | 10,000 | about 1.3×1030 |
A computer doing a billion steps a second takes about a second for 230 steps, but 2100 steps would take far longer than the age of the universe. Making the computer a thousand times faster changes that only by three orders of magnitude out of thirty. This is why an exponential algorithm is described as unusable for large inputs whatever hardware it runs on, while a polynomial one can be rescued by faster hardware.
Logarithmic growth is the opposite extreme. Binary search on a sorted list of 1,000,000 items needs at most 20 comparisons, because 220=1,048,576 is the first power of two above a million. Doubling the list to 2,000,000 items adds one comparison.
Reading complexity from code
A few patterns cover most cases.
- A single loop from 1 to n doing constant work inside is O(n).
- A loop nested inside another, both running to n, is O(n2).
- A loop in which the control variable is halved or doubled each pass (while i < n: i = i * 2) is O(logn).
- A loop over n items that calls an O(logn) operation each time, such as a binary search, is O(nlogn).
- Steps done one after another add, and the larger term wins: an O(n) pass followed by an O(n2) pass is O(n2).
- A loop whose bound does not depend on the input (run exactly 1,000 times) is O(1).
Recursion is analysed by how many calls are made and how much work each does. A recursive function that calls itself twice on inputs only one smaller, like the naive Fibonacci below, makes a number of calls that roughly doubles with each increase in n.
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)The call tree for fib(5) already repeats fib(3) twice and fib(2) three times. The total number of calls grows exponentially, about 1.6n, so fib(50) is out of reach this way while a loop that keeps the last two values does the job in O(n) steps.
Space complexity
Space complexity counts the extra memory used. The largest-value function uses a few variables whatever the size of the list, so it is O(1) in space. Merge sort needs a second array to merge into, so it uses O(n) extra space. A recursive function that goes n calls deep uses O(n) space for its call stack even if it stores nothing else.
Time and space often trade against each other. Storing results already calculated (memoisation) removes the repeated work in the Fibonacci example, turning exponential time into linear time at the price of O(n) memory.
Other bounds
Big O is an upper bound, and two companions exist for completeness. Big Omega, Ω(g(n)), is a lower bound: the algorithm takes at least this much. Big Theta, Θ(g(n)), says both hold, so the growth is exactly of that order. Saying a linear search is O(n2) is technically true but uninformative; the useful statement is the tightest bound, and for searching an unsorted list that is Θ(n) in the worst case.
و40 أخرى: افتح أياً منها من القائمة أعلاه.
التقييمات
لا توجد مراجعات مكتوبة بعد. أضف هذه الملاحظات إلى مجموعتك، ويمكنك أن تكون أول من يكتب مراجعة.