1. Basic Concepts
|
|
1.1 Allocation and deallocation of memory |
|
int main()
{
int i, *pi;
if ( !(pi = (int *)malloc(sizeof(int))) )
{
fprintf(stderr, “Insufficient memory”);
exit(0);
}
*pi = 3;
printf(“%d\n”, *pi);
free(pi);
return 0;
} |
|
|
1.2 Algorithm Specification |
|
Definition: An algorithm is a finite set of instructions that, if followed, accomplishes a particular task. In addition, all algorithms must satisfy the following criteria. |
1) Input. There are zero or more quantities that are externally supplied.
2) Output. At least one quantity is produced.
3) Definiteness. Each instruction is clear and unambiguous.
4) Finiteness. If we trace out the instructions of an algorithm, then for all cases, the algorithm terminates after a finite number of steps.
5) Effectiveness. Every instruction must be basic enough to be carried out, in principle, by a person using only pencil and paper. It is not enough that each operation be definite as in 3); it also must be feasible. |
|
In computational theory, one distinguishes between an algorithm and a program, the latter of which does not have to satisfy the fourth condition. For example, we can think of an operating system that continues in a wait loop until more jobs are entered. |
|
Example |
|
[Selection sort] Suppose we must devise a program that sorts a set of n ≥ 1 integers.
STEP 1. From those integers that are currently unsorted, find the smallest and place it next in the sorted list.
STEP 2. Write it partially in C and partially in English |
|
for (i=0; i<n; i++)
{
Examine list[i] to list[n-1] and suppose that
the smallest integer is at list[min];
Interchange list[i] and list[min];
} |
|
|
#include <stdio.h>
#include <stdlib.h> // rand()
#define SWAP(x, y, t) ((t)=(x), (x)=(y), (y)=(t))
void sort(int list[], int n);
int main(void)
{
int i, list[100];
for (i=0; i<100; i++) list[i] = rand() % 1000;
sort(list, i);
for (i=0; i<100; i++) printf("%d\n", list[i]);
return 0;
}
void sort(int list[], int n)
{
int i, j, min, temp;
for (i=0; i<n-1; i++) {
min = i;
for (j=i+1; j<n; j++)
if (list[j]<list[min]) min = j;
SWAP(list[i], list[min], temp);
}
} |
|
|
1.3 Performance Analysis |
|
One of the goals of this course to develop your skills for making evaluative judgments about programs. |
1) Does the program meet the original specifications of the task?
2) Doest it work correctly?
3) Doest the program contain documentation that shows how to use it and how it works?
4) Doest the program effectively use functions to create logical units?
5) Is the program’s code readable?
6) Does the program efficiently use primary and secondary storage?
7) Is the program’s running time acceptable for the task? |
These criteria focus on performance evaluation, we can loosely divide into two distinct fields:
space complexity and time complexity. |
|
1.3.1 Space Complexity |
|
The amount of memory that it needs to run to completion. |
Fixed space requirement |
– Space requirements that do not depend on the number and size of the program’s input and outputs.
– Include the instruction space, space for simple variables, fixed-size structured variables (such as structs), and constants. |
Variable space requirement |
– The space needed by structured variables whose size depends on the particular instance, I, for the problem being solved.
– Include the additional space required when a function uses recursion. |
The total space requirement = fixed + variable |
S(P) = c + SP(I) |
– c: constant representing the fixed space requirements.
– SP(I) : the variable space requirement of a program P working on an instance I. It is represented by SP(n) if n is the only instance characteristic of the instance I. |
|
Example: summing a list of numbers |
|
Iterative function: Ssum(n) = 0 |
float sum(float list[], int n)
{
int i; float tempsum = 0;
for (i=0; i<n; i++) tempsum += list[i];
return tempsum;
} |
|
|
Recursive function: Srsum(n) = 12*n bytes |
float rsum(float list[], int n)
{
if (n) return rsum(list, n-1) + list[n-1];
return 0;
} |
|
|
Type |
Name |
Number of bytes |
array pointer |
list[ ] |
4 |
integer |
n |
4 |
return address |
|
4 |
Total per recursive call |
|
12 |
|
|
1.3.2 Time Complexity |
|
The amount of computer time that it needs to run to completion.
The time, T(P) taken by a program, P,
T(P) = compile time + TP(I) |
– The compile time is similar to the fixed space component.
– TP(I): program run (or execution) time |
Machine-dependent estimate of TP(I) |
– Not easy task because it
– Letting n denote the instance characteristic, we might express
TP(n) = caADD(n) + csSUB(n) + clLDA(n) + cstSTA(n)
– where are constants that refer to the time needed to perform each operation, and ADD, SUB, LDA, STA are number of additions, subtractions, loads, and stores that are performed.
|
Machine-independent estimate of TP(I) |
– Program step
|
|
Program Step |
|
Definition: A program step is a syntactically or semantically meaningful program segment whose execution time is independent of the instance characteristics. |
|
Step count for summing |
|
|
|
Step count for recursive summing |
|
|
|
Step count for summing |
|
|
|
1.4 Asymptotic Notation |
|
Definition: [Big “oh”] f(n) = O(g(n)) (read as “f of n is big oh g of n”) iff (if and only if) there exist positive constants c and n0 such that f(n) ≤ cg(n) for all n, n ≥ n0. |
|
Example |
|
3n+2 = O(n) |
3n+2 ≤ 4n for all n ≥ 2 |
100n+6 = O(n) |
100n+6 ≤ 101n for all n ≥ 10 |
10n2+4n+2 = O(n2) |
10n2+4n+2 ≤ 11n2 for all n ≥ 5 |
6*2n+n2 = O(2n) |
6*2n+n2 ≤ 7*2n for all n ≥ 4 |
|
|
O(1) |
a computing time is constant |
O(n) |
linear |
O(n2) |
quadratic |
O(n3) |
cubic |
O(2n) |
exponential |
|
|
The seven computing times |
– O(1), O(log n), O(n), O(n log n), O(n2), O(n3), O(2n)
|
|
|
|
1.5 Performance Measurement |
|
We discuss on measuring time.
There are actually two different methods for timing events in C, by using C’s standard library accessed through #include <time.h> |
Method 1: clock() |
– This function gives the amount of processor time, as the built-in type clock_t, that has elapsed since the program began running.
|
Method 2: time() |
– This function returns the time, measured in seconds, as the built-in type time_t.
|
|
|
Method 1 |
Method 2 |
Start timing |
start = clock(); |
start = time(NULL); |
Stop timing |
stop = clock(); |
stop = time(NULL); |
Type returned |
clock_t |
time_t |
Result in seconds |
duration =
((double)(stop-start))
/CLOCKS_PER_SEC; |
duration =
(double)
difftime(stop, start); |
|
|
Example: timing program for worst-case sorting |
|
O(n) vs O(n2) |
#include <stdio.h>
#define MAX_SIZE 1001
void sort(int list[], int n);
int main(void)
{
int i, n, step = 10;
int a[MAX_SIZE];
double duration;
clock_t start;
for (n=0; n<MAX_SIZE; n+=step) {
for (i=0; i<n; i++)
a[i] = n-i;
start = clock();
sort(a, n);
duration = ((double)(clock()-start))/CLOCK_PER_SEC;
printf(“%d\t%f\n”, n, duration);
if (n==100)
step = 100;
}
return 0;
} |
|
|