Programmeringsmetodik: Inlämningsuppgift 2, Komplexitetsteori

Den här uppgiften går ut på att öva komplexitetsteori och tidskomplexitet. Uppgiften går ut på att bestämma tidskomplexiteten för ett antal funktioner.

Läs först introduktionen till komplexitetsteori.

Redovisning

Denna uppgift redovisas för Thomas, inte övningsassistenten. Redovisa svaret på papper, eller med e-post till thomas.padron-mccarthy@oru.se.

Om samarbete på inlämningsuppgifterna: Varje grupp (som normalt består av en eller två studenter) ska göra en egen lösning, och skicka in den, men det är inte förbjudet att samarbeta eller fråga andra studenter om hjälp. Däremot ska man i så fall tydligt ange vilka som man samarbetat med. Varje lösning måste ange namnet på alla som bidrog i arbetet. Samarbete är alltså tillåtet, men måste redovisas.

Uppgiften

Ange för var och en av följande funktioner vilken tidskomplexitet den har. Det är parametern length, och i förekommande fall stränglängden, som är det n som man brukar ange tidskomplexitet med.

Tips: Det är inte meningen att man ska provköra alla funktionerna och mäta tiden, utan det går att sluta sig till tidskomplexiteten bara genom att studera programkoden. Därför lämpar sig uppgiften bra som hemuppgift. (Därmed inte sagt att man inte får provköra. Här finns en fil med alla funktionerna, och exempel på anrop: inl2funktioner.c)

Ett tips till: Glöm inte att först läsa introduktionen till komplexitetsteori.

1. Funktionen "find_max_in_array"

// Finds the largest value in the array "a" of length "length"
double find_max_in_array(double a[], int length) {
    double max = a[0];
    for (int i = 1; i < length; ++i) {
        if (a[i] > max) {
            max = a[i];
        }
    }
    return max;
}

2. Funktionen "incorrect_reverse_string"

// Reverses the string "s" in place, but there is a bug
void incorrect_reverse_string(char* s) {
    int n = strlen(s);
    for (int i = 0; i < n; ++i) {
        char temp = s[i];
        s[i] = s[n - i - 1];
        s[n - i - 1] = temp;
    }
}

3. Funktionen "reverse_string"

// Reverses the string "s" in place
void reverse_string(char* s) {
    int n = strlen(s);
    for (int i = 0; i < n / 2; ++i) {
        char temp = s[i];
        s[i] = s[n - i - 1];
        s[n - i - 1] = temp;
    }
}

4. Funktionen "arrays_are_equal"

// Compares two arrays of length "length" and returns 1 if they are equal
double arrays_are_equal(double a[], double b[], int length) {
    for (int i = 0; i < length; ++i) {
        if (a[i] != b[i]) {
            return 0;
        }
    }
    return 1;
}

5. Funktionen "find_number_of_matches"

// Returns the sum of how many times each needle occurs in the haystack,
// both arrays of length "length"
int find_number_of_matches(int needles[], int haystack[], int length) {
    int nr_matches = 0;
    for (int n = 0; n < length; ++n) {
        for (int h = 0; h < length; ++h) {
            if (needles[n] == haystack[h]) {
                ++nr_matches;
            }
        }
    }
    return nr_matches;
}

6. Funktionen "sort_array"

// Sorts the array "a" of length "length" in ascending order using selection sort
void sort_array(double a[], int length) {
    for (int sorted = 0; sorted < length - 1; ++sorted) {
        int smallest_in_rest = sorted;
        for (int in_rest = sorted + 1; in_rest < length; ++in_rest) {
            if (a[in_rest] < a[smallest_in_rest]) {
                smallest_in_rest = in_rest;
            }
        }
        double temp = a[sorted];
        a[sorted] = a[smallest_in_rest];
        a[smallest_in_rest] = temp;
    }
}

7. Funktionen "is_array_sorted"

// Returns 1 if the array "a" of length "length" is sorted in ascending order
int is_array_sorted(double a[], int length) {
    for (int i = 0; i < length - 1; ++i)
        if (a[i] > a[i + 1])
            return 0;
    return 1;
}

8. Funktionen "is_array_sorted_2"

// Returns 1 if the array "a" of length "length" is sorted in ascending order
int is_array_sorted_2(double a[], int length) {
    double *copy = malloc(length * sizeof(double));
    memcpy(copy, a, length * sizeof(double));
    sort_array(copy, length);
    int result = arrays_are_equal(a, copy, length);
    free(copy);
    return result;
}

9. Funktionen "shuffle_array"

// Sorts the array "a" of length "length" in random order
void shuffle_array(double a[], int length) {
    for (int randomized = 0; randomized < length; ++randomized) {
        // Select a random position in the rest of the array
        int selected = randomized + rand() % (length - randomized);
        // Swap the current position with the random position
        double oldvalue = a[randomized];
        a[randomized] = a[selected];
        a[selected] = oldvalue;
    }
}

10. Funktionen "shuffle_array_really_well"

// Sorts the array "a" of length "length" in random order, but more thoroughly
void shuffle_array_really_well(double a[], int length) {
    shuffle_array(a, length);
    shuffle_array(a, length);
    shuffle_array(a, length);
}

11. Funktionen "shuffle_array_really_really_well"

// Sorts the array "a" of length "length" in random order, even more thoroughly
void shuffle_array_really_really_well(double a[], int length) {
    shuffle_array(a, length);
    shuffle_array(a, length);
    shuffle_array(a, length);
    shuffle_array(a, length);
    shuffle_array(a, length);
}

12. Funktionen "shuffle_array_really_really_really_well"

// Sorts the array "a" of length "length" in random order, ridiculously well
void shuffle_array_really_really_really_well(double a[], int length) {
    for (int i = 0; i < length; ++i)
        shuffle_array(a, length);
}

13. Funktionen "shuffle_array_really_really_really_really_well"

// Sorts the array "a" of length "length" in random order, even more ridiculously well
void shuffle_array_really_really_really_really_well(double a[], int length) {
    shuffle_array(a, length);
    shuffle_array_really_well(a, length);
    shuffle_array_really_really_well(a, length);
    shuffle_array_really_really_really_well(a, length);
}

14. Funktionen "bogosort_array"

// Sorts the array "a" of length "length" in ascending order using bogosort
void bogosort_array(double a[], int length) {
    while (! is_array_sorted(a, length))
        shuffle_array(a, length);
}

15. "Really, really well"?

(Den här uppgiften handlar inte om komplexitet.)
Är det meningsfullt att slumpa ordningen på arrayen mer än en gång, som i shuffle_array_really_well med flera? Blir blandningen verkligen bättre?


Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 23 augusti 2012