Πιθανοτικοί αλγόριθμοι

Οι περισσότεροι αλγόριθμοι που χρησιμοποιούμε στους διαγωνισμούς πληροφορικής ανήκουν στην κατηγορία των ντετερμινιστικών αλγορίθμων. Αυτό σημαίνει ότι η συμπεριφορά τους θα είναι πάντα η ίδια, όταν η είσοδός τους είναι η ίδια (ως συμπεριφορά δεν ορίζουμε μόνο την έξοδο του προγράμματος, αλλά όλα τα ενδιάμεσα βήματα από τα οποία θα περάσει). Υπάρχουν όμως μερικοί πιθανοτικοί αλγόριθμοι οι οποίοι είναι αρκετά χρήσιμοι στους διαγωνισμούς πληροφορικής.

Για να παραγάγουμε τυχαίο αριθμό στις γλώσσες c και c++ θα χρησιμοποιούμε τις βιβλιοθήκες stdlib.h και time.h. Στην αρχή του προγράμματός μας θα βάζουμε (μόνο μία φορά) srand(time(NULL)) και κάθε φορά που θα χρειαζόμαστε έναν τυχαίο αριθμό θα καλούμε τη συνάρτηση rand(). Για παράδειγμα το παρακάτω πρόγραμμα διαβάζει έναν αριθμό $n$ και τυπώνει έναν τυχαίο αριθμό στο διάστημα $[0,n-1]$:

#include <stdio.h> // scanf, printf
#include <stdlib.h> // srand, rand
#include <time.h> // time

int main() {
    srand(time(NULL));
    int n;
    scanf("%d", &n);
    printf("%d\n", rand()%n);
    return 0;
}

• Quicksort
• Merge heap
• Treap
  • Καρτεσιανό δέντρο
  • Treap
    • Merge
    • Split
    • Implicit Treap
    • Lazy Propagation
• Χρήσιμα μαθηματικά
• Προβλήματα με λύσεις
  • Monte (BOSPRE 2016, παραλλαγή)
  • Quickselect
• Εκτός ύλης
  • Ο Αλγόριθμος του Freivalds
  • Αποδείξεις
    • Απόδειξη της αναμενόμενης πολυπλοκότητας της quicksort
    • Απόδειξη της πολυπλοκότητας της merge heap
    • Απόδειξη της αναμενόμενης πολυπλοκότητας της treap
• Προβλήματα
• Πηγές

Quicksort

Η quicksort είναι ένας αλγόριθμος ταξινόμησης. Αν και δεν χρειάζεται να τον ξέρουμε για διαγωνισμούς πληροφορικής (καθώς μπορούμε να χρησιμοποιούμε έτοιμες εντολές όπως η sort της c++), είναι μια καλή εισαγωγή στους αλγορίθμους τυχαιότητας.

Ας υποθέσουμε ότι είχαμε έναν τρόπο, δεδομένου ενός πίνακα στοιχείων, να βρούμε σε $O(1)$ το median όλων των στοιχείων. Τότε θα μπορούσαμε να κατασκευάσουμε τον εξής αλγόριθμο:

1. Έστω $m$ το μεσαίο στοιχείο (median)
2. Διατρέχουμε όλον τον πίνακα και φροντίζουμε όσα στοιχεία είναι μικρότερα του $m$ να βρεθούν αριστερά του, ενώ όσα είναι μεγαλύτερά του να βρεθούν δεξιά του
3. Χωρίζουμε τον πίνακα σε δύο υποπίνακες, τα στοιχεία αριστερά του $m$ και τα στοιχεία δεξιά του, και για τον κάθε υποπίνακα ξεκινάμε από το βήμα 1.

Αφού το $m$ είναι το median, ο κάθε υποπίνακας θα έχει μέγεθος ίσο με το μισό του αρχικού πίνακα. Άρα, η πολυπλοκότητα είναι $T(n)=2T(\frac{n}{2})+O(n)=O(n\log n)$ σύμφωνα με το Master Theorem.

Δυστυχώς δεν υπάρχει τρόπος σε $O(1)$ να βρούμε το median όλων των στοιχείων. Όμως, εάν αντί να διαλέγουμε το median, επιλέγουμε ένα τυχαίο στοιχείο, αποδεικνύεται ότι η πολυπλοκότητα παραμένει η ίδια.

void quicksort(int *arr, int n) {
    if(n<=1) {
        return;
    }
    int m=rand()%n;
    swap(arr[0], arr[m]);
    m=0;
    for(int i=1; i<n; ++i) {
        if(arr[i]<arr[m]) {
            swap(arr[m+1], arr[i]);
            swap(arr[m], arr[m+1]);
            ++m;
        }
    }
    quicksort(arr, m);
    quicksort(arr+m+1, n-m-1);
}

Merge heap

Η merge heap (ή αλλιώς meld heap) είναι ένας εναλλακτικός τρόπος να υλοποιήσουμε ένα heap. Υπενθυμίζουμε ότι τα heap υποστηρίζουν τις εξής πράξεις:

• Insert(val): Εισάγει την τιμή val στη δομή
• Find-min(): Επιστρέφει την ελάχιστη τιμή της δομής
• Delete-min(): Αφαιρεί την ελάχιστη τιμή από τη δομή

Σε αντίθεση όμως με τον συνηθισμένο τρόπο υλοποίησης, ο κώδικας είναι πολύ μικρός, και όλες οι πράξεις γίνονται με τη χρήση μίας και μόνο πράξης:

• Merge(h1, h2): Επιστρέφει ένα heap το οποίο είναι η ένωση των h1 και h2.

Επομένως μπορούμε να υλοποιήσουμε τις παραπάνω βασικές πράξεις ως εξής:

• Insert(val): Δημιουργούμε ένα καινούριο heap (έστω h1) το οποίο περιέχει μόνο ένα στοιχείο με τιμή val και κάνουμε h=Merge(h1, h), όπου h είναι η heap μας.
• Find-min(): Όπως θα δούμε μπορούμε να το βρούμε σε $O(1)$ διότι γνωρίζουμε ανά πάσα στιγμή την κορυφή της heap.
• Delete-min(): Αν η heap μας είναι η h, και τα αριστερά και δεξιά παιδιά της κορυφής είναι οι h->l και h->r αντίστοιχα, τότε θέτουμε h=Merge(h->l, h->r).

Αποδεικνύεται ότι η πράξη Merge γίνεται σε $O(\log n)$.

struct heap {
    heap *l, *r;
    int val;
} *h;
heap* merge(heap *h1, heap *h2) {
    if(h1==NULL) {
        return h2;
    }
    if(h2==NULL) {
        return h1;
    }
    if(h2->val < h1->val) {
        swap(h1, h2);
    }
    if(rand()%2==1) {
        swap(h1->l, h1->r);
    }
    h1->l=merge(h1->l, h2);
    return h1;
}

Επομένως όλες οι πράξεις γίνονται ως εξής:

void insert(int val) {
    heap *h1=(heap*)malloc(sizeof(heap));
    h1->l=NULL;
    h1->r=NULL;
    h1->val=val;
    h=merge(h1, h);
}
int find_min() {
    return h->val;
}
void delete_min() {
    h=merge(h->l, h->r);
}

Treap

Η treap (σε αντίθεση με τους αλγορίθμους που έχουμε παραθέσει μέχρι τώρα) είναι ιδιαίτερα χρήσιμη δομή στους διαγωνισμούς πληροφορικής. Είναι ένα ισορροπημένο δέντρο δυαδικής αναζήτησης (balanced binary search tree). Ο λόγος που ονομάζεται treap είναι διότι ταυτόχρονα είναι heap και binary search tree.

Καρτεσιανό δέντρο

Το καρτεσιανό δέντρο είναι ένα δυαδικό δέντρο το οποίο δημιουργείται βάσει ενός πίνακα αριθμών. Είναι heap όσον αφορά τις τιμές του πίνακα (δηλαδή η μικρότερη τιμή του πίνακα αντιστοιχεί στην κορυφή του καρτεσιανού δέντρου) και binary search tree όσον αφορά τη θέση του στοιχείου στον πίνακα. Για παράδειγμα, ο πίνακας $(6, 10, 3, 20, 43, 1, 2, 4, 11, 5)$ αντιστοιχεί στο παρακάτω δυαδικό δέντρο:

Εάν οι τιμές του πίνακα είναι ανά δύο διαφορετικές, τότε η αναπαράσταση ως καρτεσιανό δέντρο είναι μοναδική.

Treap

Η treap είναι ουσιαστικά ένα καρτεσιανό δέντρο το οποίο έχει τυχαίες τιμές στα κελιά του. Συγκεκριμένα, αντί για πίνακα, έχουμε $n$ ζευγάρια στοιχείων που αποτελούνται από το κλειδί (key) και την προτεραιότητα (priority). Τα κλειδιά είναι για το treap ό,τι οι θέσεις στον πίνακα ήταν για το καρτεσιανό δέντρο, και οι προτεραιότητες ό,τι ήταν οι τιμές στον πίνακα. Επομένως το treap είναι heap όσον αφορά τις προτεραιότητες, και heap όσον αφορά τις τιμές. Εξακολουθεί να ισχύει το γεγονός ότι εάν τα κλειδιά και οι προτεραιότητες είναι μοναδικές, τότε υπάρχει μοναδικό treap που αντιστοιχεί σε αυτά. Ένα παράδειγμα treap είναι το εξής:

Όπως όλα τα δέντρα δυαδικής αναζήτησης, η treap υποστηρίζει τις εξής βασικές πράξεις:

• Insert(val): Εισάγει την τιμή val στο δέντρο.
• Search(val): Εξετάζει αν η τιμή val βρίσκεται στο δέντρο.
• Delete(val): Εάν υπάρχει η τιμή val στο δέντρο, τη σβήνει.

Η σημαντικότερη ιδιότητα όμως της treap είναι ότι όλες τις πράξεις που υποστηρίζουν τα δέντρα δυαδικής αναζήτησης (και μερικές ακόμα) χρησιμοποιώντας μόνο δύο πράξεις, merge και split. Αυτό τα κάνει ιδιαίτερα εύκολα στην υλοποίηση και ιδανικά για διαγωνισμούς πληροφορικής.

• Merge(t, t1, t2): Δεδομένου του ότι όλα τα στοιχεία της treap t1 είναι μικρότερα από όλα τα στοιχεία της t2, ενώνει τις δύο treap και τις αποθηκεύει στην t.
• Split(t, t1, t2, val): Δημιουργεί δύο νέες treap t1, t2 από τα στοιχεία της t, έτσι ώστε όλα τα στοιχεία της t1 να είναι μικρότερα ή ίσα του val και όλα τα στοιχεία της t2 να είναι μεγαλύτερα.

Αποδεικνύεται ότι και οι δύο αυτές πράξεις γίνονται σε $O(\log n)$.

Θα υλοποιήσουμε την treap με τη χρήση pointers και structs της c++.

#define MAXPRIOR 0x3f3f3f3f
struct el {
    el *left, *right;
    int prior, key;
      
    el(int key) {
        left=NULL;
        right=NULL;
        this->key=key;
        prior=rand()%MAXPRIOR;
    }
} *root;
typedef treept el*;

Merge

Ας εξετάσουμε πρώτα πώς δουλεύει η Merge. Έχοντας δύο treaps, θέλουμε να παραγάγουμε μία treap η οποία να έχει όλα τα στοιχεία των δύο treaps. Ξεκινώντας από τις κορυφές, ελέγχουμε ποια από τις δύο κορυφές των treaps έχει μεγαλύτερη προτεραιότητα (άρα και θα πρέπει να είναι πιο πάνω). Εάν είναι η κορυφή της treap με τα μικρά κλειδιά, τότε ξέρουμε ότι όλα τα στοιχεία της treap με τα μεγάλα κλειδιά θα είναι στο δεξί υπόδεντρο της treap με τα μικρά κλειδιά, οπότε και μπορούμε να κάνουμε αναδρομικά Merge το δεξί παιδί της μικρής treap με την μεγάλη treap. Αντίστοιχα, εάν η κορυφή της treap με τα μεγάλα στοιχεία έχει την μικρότερη προτεραιότητα, τότε γνωρίζουμε ότι όλα τα στοιχεία της treap με τα μικρά στοιχεία θα είναι στο αριστερό υπόδεντρο της treap με τα μεγάλα στοιχεία. Για παράδειγμα, εάν κάνουμε Merge τα treaps $\{(9,5), (14,68), (16,19), (19,27)\}$ και $\{(20,30), (22,13), (23,48)\}$ έχουμε:

Ακολουθεί ο κώδικας:

void Merge(treept &now, treept lft, treept rgt) {
    if(lft==NULL) {
        now=rgt;
        return;
    }
    if(rgt==NULL) {
        now=lft;
        return;
    }
      
    if(lft->prior>rgt->prior) {
        Merge(rgt->left, lft, rgt->left);
        now=rgt;
    }
    else {
        Merge(lft->right, lft->right, rgt);
        now=lft;
    }
}

Split

Το Split ακολουθεί την αντίθετη διαδικασία με το Merge. Υπενθυμίζουμε ότι το Split χωρίζει ένα treap με βάση ένα κλειδί σε δύο treaps. Συγκρίνει την τιμή με την οποία χωρίζουμε με το κλειδί της κορυφής. Εάν το κλειδί της κορυφής είναι μικρότερο ή ίσο της τιμής με την οποία χωρίζουμε, τότε ξέρουμε ότι η κορυφή και το αριστερό της υπόδεντρο θα ανήκουν στην treap με τα μικρά κλειδιά, οπότε μπορούμε να καλέσουμε αναδρομικά Split στο δεξί παιδί της κορυφής για να βρούμε ποια κλειδιά πρέπει να μεταφερθούν στην treap με τα μεγάλα κλειδιά. Αντίστοιχα, εάν το κλειδί της κορυφής είναι μεγαλύτερο της τιμής με την οποία χωρίζουμε, τότε ξέρουμε ότι η κορυφή μαζί με το δεξί της παιδί θα ανήκουν στην treap με τα μεγάλα κλειδιά, οπότε πρέπει να καλέσουμε Split στο αριστερό υπόδεντρο της κορυφής. Το παρακάτω παράδειγμα αναπαριστά το Split στην treap $\{(10,26), (13,17), (17,20), (25,19), (30,25)\}$ στην τιμή $17$.

Ακολουθεί ο κώδικας:

void Split(treept now, treept &lft, treept &rgt, int key) {
    if(now==NULL) {
        lft=NULL;
        rgt=NULL;
        return;
    }
      
    if(now->key<=key) {
        Split(now->right, now->right, rgt, key);
        lft=now;
    }
    else {
        Split(now->left, lft, now->left, key);
        rgt=now;
    }
}

Αφού ορίσαμε το Split και το Merge, μπορούμε να δούμε πώς ορίζονται οι υπόλοιπες βασικές πράξεις σύμφωνα με αυτά:

void Insert(int val) {
    treept newel=new el(val), t;
    Split(root, root, t, val);
    Merge(root, root, newel);
    Merge(root, root, t);
}
bool Search(int val) {
    treept t1, t2;
    bool out=false;
    Split(root, root, t2, val);
    Split(root, t1, root, val);
    if(root!=NULL && root->val==val) {
        out=true;
    }
    Merge(root, t1, root);
    Merge(root, root, t2);
    return out;
}
void Delete(int val) {
    treept t1, t2;
    Split(root, root, t2, val);
    Split(root, t1, root, val);
    Merge(root, t1, t2);
}

Implicit Treap

Εάν θέλουμε να κάνουμε πράξεις αναφερόμενοι σε θέσεις και όχι σε κλειδιά, μπορούμε να τροποποιήσουμε την συνάρτηση Split έτσι ώστε να κόβουμε το δέντρο, όχι με βάση κάποια τιμή, αλλά έτσι ώστε το δέντρο με τα μικρά κλειδιά να έχει ακριβώς $k$ στοιχεία. Επειδή όμως χρειάζεται να αποθηκεύουμε το μέγεθος του κάθε υποδέντρου, παρουσιάζουμε εξ’αρχής τον κώδικα τροποποιημένο.

struct el {
    el *left, *right;
    int prior, key, siz;
      
    el(int key) {
        left=NULL;
        right=NULL;
        siz=0;
        this->key=key;
        prior=rand()%MAXPRIOR;
    }
} *root;
int tr_size(treept now) {
    if(now==NULL) {
        return 0;
    }
    return now->siz;
}
void upd(treept &now) {
    if(now==NULL) {
        return;
    }
    now->siz=tr_size(now->left)+tr_size(now->right)+1;
}
void Merge(treept &now, treept lft, treept rgt) {
    if(lft==NULL) {
        now=rgt;
        return;
    }
    if(rgt==NULL) {
        now=lft;
        return;
    }
      
    if(lft->prior>rgt->prior) {
        Merge(rgt->left, lft, rgt->left);
        now=rgt;
    }
    else {
        Merge(lft->right, lft->right, rgt);
        now=lft;
    }
    upd(now);
}
void Implicit_split(treept now, treept &lft, treept &rgt, int key, int offset=0) {
    if(now==NULL) {
        lft=NULL;
        rgt=NULL;
        return;
    }
      
    int implkey=offset+tr_size(now->left);
    if(implkey<=key) {
        Implicit_split(now->right, now->right, rgt, key, offset+tr_size(now->left)+1);
        lft=now;
    }
    else {
        Implicit_split(now->left, lft, now->left, key, offset);
        rgt=now;
    }
    upd(lft);
    upd(rgt);
}

Lazy Propagation

Όπως και σε άλλες δομές, μπορούμε να κάνουμε πράξεις πάνω σε treaps, όπως να προσθέσουμε τιμές σε όλα τα στοιχεία σε ένα εύρος. Υπάρχει όμως μία πράξη η οποία είναι χαρακτηριστική για τα treaps, καθώς η πρώτη φορά που εμφανίστηκαν τα implicit treaps ήταν για να εφαρμόσουν αυτήν την πράξη. Η πράξη αυτή είναι το Reverse, το οποίο αντιστρέφει τη σειρά στοιχείων σε ένα εύρος. Δείχνοντας πώς να υλοποιήσουμε την πράξη αυτή, θα γίνει εμφανές πώς δουλεύει το lazy propagation στα treaps. Παραθέτουμε την υλοποίηση της καινούριας συνάρτησης Reverse, καθώς και τις αλλαγές στον υπάρχοντα κώδικα, οι οποίες χρειάζονται για το lazy propagation.

struct el {
    el *left, *right;
    int prior, key, siz;
    bool islazy;
      
    el(int key) {
        left=NULL;
        right=NULL;
        siz=0;
        islazy=false;
        this->key=key;
        prior=rand()%MAXPRIOR;
    }
} *root;
void propagate(treept now) {
    if(now==NULL || !now->islazy) {
        return;
    }
    swap(*(now->left), *(now->right));
    if(now->left!=NULL) {
        now->left->islazy^=true;
    }
    if(now->right!=NULL) {
        now->right->islazy^=true;
    }
    now->islazy=false;
}
void Merge(treept &now, treept lft, treept rgt) {
    if(lft==NULL) {
        now=rgt;
        return;
    }
    if(rgt==NULL) {
        now=lft;
        return;
    }
    propagate(lft);
    propagate(rgt);
      
    if(lft->prior>rgt->prior) {
        Merge(rgt->left, lft, rgt->left);
        now=rgt;
    }
    else {
        Merge(lft->right, lft->right, rgt);
        now=lft;
    }
    upd(now);
}
void Implicit_split(treept now, treept &lft, treept &rgt, int key, int offset=0) {
    if(now==NULL) {
        lft=NULL;
        rgt=NULL;
        return;
    }
    propagate(now);
      
    int implkey=offset+tr_size(now->left);
    if(implkey<=key) {
        Implicit_split(now->right, now->right, rgt, key, offset+tr_size(now->left));
        lft=now;
    }
    else {
        Implicit_split(now->left, lft, now->left, key, offset);
        rgt=now;
    }
    upd(lft);
    upd(rgt);
}
void Reverse(int from, int to) {
    treept t1, t2;
    Implicit_split(root, root, t2, to);
    Implicit_split(root, t1, root, from-1);
    root->islazy^=true;
    Merge(root, t1, root);
    Merge(root, root, t2);
}

Χρήσιμα μαθηματικά

• Η αναμενόμενη (expected) τιμή μιας τυχαίας μεταβλητής $X$ συμβολίζεται ως $\mathbb{E}(X)$ και ορίζεται ως $\sum_{s\in S} {s\cdot\mathbb{P}(X=s)}$, όπου $\mathbb{P}(X=s)$ είναι η πιθανότητα το $X$ να έχει τιμή $s$.
• Εάν κάτι συμβαίνει με πιθανότητα $p$, τότε η αναμενόμενη τιμή ανεξάρτητων δοκιμών που χρειάζονται για να εξασφαλίσουμε μεγάλη πιθανότητα ότι θα συμβεί είναι $\frac{1}{p}$.
• Για τυχαίο, μη αρνητικό ακέραιο $X$ ισχύει $\mathbb{E}(X)=\sum_{k=0}^{\infty} {\mathbb{P}(X>k)}$.
• Ισχύει $\mathbb{E}(aX+bY)=a\mathbb{E}(X)+b\mathbb{E}(Y)$.
• Ανισότητα του Μαρκόβ: Για μη αρνητικό τυχαίο $X$ και $\lambda>0$, ισχύει ότι $\mathbb{P}(X>\lambda \mathbb{E}(X))<\frac{1}{\lambda}$.

Προβλήματα με λύσεις

Monte (BOSPRE 2016, παραλλαγή)

Εκφώνηση: Εάν θεωρήσουμε τουλάχιστον $2$, και το πολύ $k$ στοιχεία στο εύρος $(0,1)$, ποια είναι η αναμενόμενη ελάχιστη απόσταση μεταξύ δύο σημείων; Δίνεται ότι $1\leq k \leq 100$, και η απάντηση να δοθεί με ακρίβεια δύο δεκαδικών ψηφίων.

Λύση: Το γεγονός ότι η απάντηση ζητείται με ακρίβεια δύο δεκαδικών ψηφίων σημαίνει ότι δεν είναι απαραίτητο να υπολογίσουμε με ακρίβεια την τιμή, αλλά μπορούμε να κάνουμε simulation. Η προφανής λύση θα ήταν για κάθε $l \in [2,k]$ να παραγάγουμε κάποιους πίνακες $l$ στοιχείων και να βρίσκαμε σε $O(l^2)$ την ελάχιστη απόσταση μεταξύ δύο σημείων, οπότε αθροιστικά έχουμε πολυπλοκότητα $O(k^3)$. Στην χειρότερη περίπτωση, έχουμε ότι $k=100$, οπότε προλαβαίνουμε να κάνουμε μόνο $100$ δοκιμές (αφού μπορούμε να κάνουμε το πολύ $100\,000\,000$ πράξεις ανά δευτερόλεπτο), που δεν είναι αρκετές. Μπορούμε όμως να ρίξουμε την πολυπλοκότητα, έτσι ώστε να προλαβαίνουμε να κάνουμε περισσότερες δοκιμές. Αντί να δημιουργούμε καινούριο πίνακα για κάθε $l$, μπορούμε να βασιστούμε στον πίνακα που δημιουργήσαμε για $l-1$. Επομένως, μπορούμε να δημιουργήσουμε ένα καινούριο στοιχείο στο εύρος $(0,1)$, και να υπολογίσουμε την νέα ελάχιστη απόσταση σε $O(l)$ (αφού δεν χρειάζεται να υπολογίσουμε ανά δύο τις αποστάσεις των υπόλοιπων στοιχείων, καθώς ήδη τις ξέρουμε από το προηγούμενο βήμα). Έτσι, έχουμε πολυπλοκότητα $O(k^2)$, άρα προλαβαίνουμε να κάνουμε $10\,000$ δοκιμές για κάθε $k$.

Σημείωση: Καθώς η c++ μπορεί να παράξει μόνο ακέραιους τυχαίους αριθμούς, θα πρέπει να βρούμε έναν τρόπο να παραγάγουμε αριθμούς στο εύρος $(0,1)$. Μία ιδέα θα ήταν να παραγάγουμε έναν τυχαίο αριθμό $r$, και να θεωρήσουμε τον αντίστροφό του $\frac{1}{r}$. Όμως, καθώς ο $r$ είναι ακέραιος, όλοι οι αριθμοί που θα παραγάγουμε θα είναι μικρότεροι του $0.5$, ή ίσοι με $1$, συνεπώς αυτός ο τρόπος δεν είναι ο σωστός. Αντ’αυτού θα πρέπει να δημιουργήσουμε έναν ακέραιο αριθμό $r$ στο εύρος $[1,10^9-1]$ και να θεωρήσουμε τον αριθμό $\frac{r}{10^9}$, οπότε για τον κάθε τυχαίο αριθμό θα χρησιμοποιούμε (rand()%(1000000000-2)+1)/1000000000).

Quickselect

Εκφώνηση: Δίνονται $n$ διαφορετικοί μεταξύ τους αριθμοί και ένας ακέραιος $1\leq k \leq n$. Να βρεθεί ο $k$-οστός μικρότερος αριθμός στον πίνακα.

Λύση: Η άμεση λύση θα ήταν να ταξινομήσουμε τον πίνακα σε $O(n\log n)$ και να επιστρέψουμε το $k$-οστό στοιχείο. Όμως μπορούμε να πετύχουμε και πολυπλοκότητα $O(n)$. Ας εξετάσουμε τον αλγόριθμο quicksort. Σε κάθε βήμα επιλέγουμε ένα τυχαίο στοιχείο, και βρίσκουμε τη σωστή θέση του στον πίνακα (καθώς εξετάζουμε όλα τα στοιχεία, και μεταφέρουμε αυτά που είναι μικρότερα στα αριστερά του, και αυτά που είναι μεγαλύτερα στα δεξιά του). Εάν ψάχνουμε το $k$-οστό στοιχείο, και το στοιχείο που μόλις βάλαμε στη σωστή του θέση είναι στη $l$ τότε υπάρχουν τρεις περιπτώσεις:

• Αν $l=k$, τότε έχουμε βρει την απάντηση.
• Αν $l<k$, τότε το στοιχείο που ψάχνουμε βρίσκεται στον δεξιό υποπίνακα (οπότε δεν χρειάζεται να επανεξετάσουμε τον αριστερό).
• Αν $l>k$, τότε το στοιχείο που ψάχνουμε βρίσκεται στον αριστερό υποπίνακα.

Μένει τώρα να αποδείξουμε την πολυπλοκότητα του αλγορίθμου αυτού.

Έστω $n_i$ το πλήθος των στοιχείων του πίνακα που έχουν απομείνει μετά το $i$-οστό βήμα της αναδρομής. Τότε, θα λέμε ότι το $i$-οστό βήμα της αναδρομής ήταν “καλό” αν $n_i\leq \frac{3}{4}n_{i-1}$. Συνεπώς έχουμε ότι $n_i\leq \left(\frac{3}{4}\right)^{g_i} n_0$, όπου $n_0$ είναι το πλήθος των στοιχείων του αρχικού πίνακα και $g_i$ είναι το πλήθος των “καλών” βημάτων της αναδρομής μέχρι το βήμα $i$. Αφού η πολυπλοκότητα της quickselect ισούται με το πλήθος των συγκρίσεων, έχουμε ότι η πολυπλοκότητα ισούται με $\sum_{i=0} n_i \leq \sum_{i=0} {\mid n_{g_{i+1}}-n_{g_i}\mid 2}n_{g_i}\leq n_0\sum_{i=0}^d{\left (\frac{3}{4}\right)^i\mid n_{g_{i+1}}-n_{g_i}\mid 2}$, όπου $d\leq \left\lceil \log_{4/3} n\right\rceil$. Αφού όμως η πιθανότητα ένα βήμα της αναδρομής να είναι καλό είναι 50%, έχουμε ότι $E[\mid n_{g_{i+1}}-n_{g_i}\mid 2$, άρα $n_0\sum_{i=0}^d {\left (\frac{3}{4}\right)^i\mid n_{g_{i+1}}-n_{g_i}\mid 2}=O(n_0)$.

Εκτός ύλης

Ο Αλγόριθμος του Freivalds

Έστω ότι έχουμε δύο πίνακες (matrices) $A,B$, μεγέθους $n\times n$ που θέλουμε να πολλαπλασιάσουμε. Προς το παρόν δεν έχει βρεθεί αλγόριθμος με πολυπλοκότητα $O(n^2)$ (Ο καλύτερος αλγόριθμος είναι αυτός του Fürer με πολυπλοκότητα $\Theta(n\log(n)2^{\Theta(\log^{*}(n))})$). Ας υποθέσουμε ότι θέλουμε απλά να επιβεβαιώσουμε το αποτέλεσμα ενός πολλαπλασιασμού (δηλαδή να ελέγξουμε αν $C=A\times B$). Προφανώς, μπορούμε να κάνουμε κανονικά τον πολλαπλασιασμό, αλλά θα προτιμούσαμε κάτι καλύτερο. Θα διαλέξουμε ένα τυχαίο διάνυσμα $x\in \{0,1\}^n$ του οποίου όλες οι συντεταγμένες είναι είτε $0$, είτε $1$. Τότε μπορούμε να ελέγξουμε αν $Cx=A(Bx)$ σε $O(n^2)$, καθώς χρειάζεται να κάνουμε μόνο πολλαπλασιασμό διανυσμάτων. Προφανώς αν $C=AB$ τότε $Cx=A(Bx)$ για κάθε $x$, όμως το ανάποδο δεν ισχύει.

Θα αποδείξουμε ότι για τυχαίο $x$, αν $C\neq A\times B$, τότε $P[Cx\neq A(Bx)]\geq 1/2$.

Έστω $D=C-A\times B$, οπότε αρκεί να δείξουμε ότι $P[Dx\neq 0] \geq 1/2$. Αφού ήδη ξέρουμε ότι $D\neq 0$, θα πρέπει να υπάρχει κάποιο $j$ έτσι ώστε η $j$-οστή στήλη να είναι μη μηδενική. Έστω ότι $D_j$ είναι η $j$-οστή στήλη. Ας θεωρήσουμε ένα $x$ για το οποίο ισχύει $Dx=0$, και έστω $x^\prime$ ένα διάνυσμα το οποίο είναι ίσο με το $x$, εκτός από την $j$-οστή του συντεταγμένη. Συνεπώς, $Dx^\prime=Dx+D_j=0+D_j\neq 0$, αφού θεωρήσαμε ότι $D_j\neq 0$. Άρα, για κάθε $x$ τέτοιο ώστε $Dx=0$, υπάρχει τουλάχιστον ένα $Dx^\prime$ τέτοιο ώστε $Dx^\prime \neq 0$. Όμως, βλέπουμε ότι αν αλλάξουμε και πάλι την $j$-οστή συντεταγμένη του $x^\prime$, θα καταλήξουμε στο $x$, συνεπώς αυτή η μετατροπή είναι αντιστρέψιμη, και άρα ένα προς ένα. Αυτό σημαίνει ότι σε κάθε $x$ για το οποίο $Dx=0$, αντιστοιχεί τουλάχιστον ένα μοναδικό $x^\prime$ έτσι ώστε $Dx^\prime\neq 0$. Άρα, πάνω από τα μισά διανύσματα είναι τέτοια ώστε $Dx\neq 0$, για κάθε μη μηδενικό $D$.

Επομένως, μπορούμε να πετύχουμε οσοδήποτε μικρή πιθανότητα σφάλματος θέλουμε, αυξάνοντας τις δοκιμές που κάνουμε. Συγκεκριμένα, αν θέλουμε να πετύχουμε πιθανότητα λάθους $P$, πρέπει να κάνουμε $k=\log\left (\frac{1}{P}\right )$ δοκιμές.

Αποδείξεις

Απόδειξη της αναμενόμενης πολυπλοκότητας της quicksort

Ας θεωρήσουμε δυο στοιχεία τα οποία στον ταξινομημένο πίνακα έχουν θέσεις $i$ και $j$ (έστω $i<j$). Τότε αναγκαστικά σε κάποιο βήμα του αλγορίθμου θα πρέπει το median που θα είχε επιλεγεί να είναι στο διάστημα $[i,j]$. Εάν το median ήταν είτε το $i$ είτε το $j$, τότε τα δύο αυτά στοιχεία θα είχαν συγκριθεί μεταξύ τους. Σε κάθε άλλη περίπτωση δεν θα είχαν συγκριθεί. Επομένως, για κάθε ζευγάρι $i,j$ με $i<j$ η πιθανότητα να συγκριθούν μεταξύ τους είναι $\frac{2}{j-i+1}$. Συνεπώς, η αναμενόμενη (expected) τιμή του πλήθους των συγκρίσεων είναι

Επομένως η πολυπλοκότητα του αλγορίθμου είναι $O(n\log n)$.

Απόδειξη της πολυπλοκότητας της merge heap

Έστω $h(T)$ το μήκος τυχαίου μονοπατιού από την κορυφή προς κάποιο φύλλο. Είναι εμφανές ότι το merge διαλέγει δύο τυχαία μονοπάτια στα δύο heaps και ακολουθεί αυτά. Άρα, έχει πολυπλοκότητα $O(h(T_1)+h(T_2))$. Αρκεί λοιπόν να υπολογίσουμε το $\mathbb{E}[h(T)]$. Θα αποδείξουμε ότι $\mathbb{E}[h(T)]\leq \log(n+1)$. Θα χρησιμοποιήσουμε επαγωγή. Έστω ότι το έχουμε αποδείξει για το αριστερό και το δεξί παιδί της κορυφής. Τότε έχουμε: $\mathbb{E}[h(T)]=1+\frac{1}{2}(\mathbb{E}[h(T_l)]+\mathbb{E}[h(T_r)]) = \log2\sqrt{(n_l+1)(n_r+1)} \leq \log{\frac{2(n_l+1)(n_r+1)}{2}}=\log(n+1)$.

Απόδειξη της αναμενόμενης πολυπλοκότητας της treap

Η απόδειξη είναι πανομοιότυπη με αυτήν της quicksort. Όπως έχουμε δει, η treap είναι ουσιαστικά ένα καρτεσιανό δέντρο, στο οποίο οι θέσεις τον σημείων είναι ίσες με τα κλειδιά της treap. Συνεπώς, στο κάθε treap (εάν συμπιέσουμε τα στοιχεία έτσι ώστε τα κλειδιά τους να είναι όλα συνεχόμενα), αντιστοιχεί ένας και μοναδικός πίνακας. Ας θεωρήσουμε αυτόν τον πίνακα. Για κάθε σημείο θέλουμε να γνωρίζουμε το αναμενόμενο βάθος του. Έστω ο πίνακας $A$ έτσι ώστε το $A_{i,j}$ να είναι ίσο με 1 αν το $j$ είναι στο υπόδεντρο του $i$, και 0 αλλιώς. Για κάθε $j$, το αναμενόμενο βάθος του είναι $\sum_{i=1}^n {A_{i,j}}$. Αρκεί λοιπόν να βρούμε τις τιμές του πίνακα αυτού. Παρατηρούμε (κοιτώντας την εικόνα του καρτεσιανού δέντρου παραπάνω), ότι το $i$ είναι πρόγονος του $j$ αν και μόνο αν το $i$ έχει την μικρότερη προτεραιότητα στο εύρος $[j,i]$ ή $[i,j]$, ανάλογα με το ποιο είναι μικρότερο. Αφού οι προτεραιότητες είναι τυχαίες, η πιθανότητα να συμβαίνει αυτό είναι $\frac{1}{\mid i-j\mid 1}$. Όπως και στην απόδειξη της πολυπλοκότητας της quicksort βλέπουμε ότι $\sum_{i=1}^n {A_{i,j}} = O(\log n)$. Επομένως το αναμενόμενο βάθος του κάθε κόμβου είναι $O(\log n)$. Αυτό σημαίνει ότι η κάθε πράξη έχει αναμενόμενη πολυπλοκότητα $O(\log n)$.

Προβλήματα

e-olymp 688

e-olymp 3615

e-olymp 4079

e-olymp 6469

Spoj CARDFLIP

Spoj CERC07S

Πηγές

Harvard CS125 lecture 18 notes

e-maxx randomized heap (μέσω google translate)

e-maxx treap (μέσω google translate)

Σχόλια