Πρόβλημα #1

[feedWARd]

Σας δίνεται ένας πίνακας Α με n ακεραίους ταξινομημένους σε αύξουσα σειρά και ένας ακέραιος c. Βρείτε αλγόριθμο που να ελέγχει αν υπάρχoυν i, j διαφορετικά μεταξύ τους, ωστέ να ισχυεί Α + A[j] = c (δηλαδή αν υπάρχουν δύο στοιχεία του πίνακα που να δίνουν άθροισμα c). Γράψτε time και memory complexity.

[chris]

Ένας δείκτης i στην αρχή του πίνακα, ένας δείκτης j στο τέλος του. Αν το άθροιμσα των στοιχείων που δείχνουν είναι μεγαλύτερο του N μειώνουμε το j, αλλιώς αυξάνουμε το i μέχρι να βρούμε την λύση. Πολυπλοκότητα μνήμης n, πολυπλοκότητα χρόνου Ν στην χειρότερη περίπτωση. ΧΑ.

[pman]

Κώδικας: Επιλογή όλων

#include <stdio.h>
#include <stdlib.h>

#define MAX 1000

int i , j , N , findu;
int a[MAX];

int main(){
 FILE*fin;
 FILE*fout;
 fin = fopen("input.in","r");
 fout = fopen("output.out","w");
 fscanf(fin,"%d %d",&N,&findu);
 for(i=0;i<N;++i)
 fscanf(fin,"%d",&a[i]);
 fclose(fin);
 
 for(i=0;i<N;++i){ if(a[i] > findu){break;}
 for(j=i+1;j<N;++j){                 
 if( a[i] + a[j] == findu){
 fprintf(fout,"%d %d\n",i+1,j+1);    
 }
 }}
 
 fclose(fout);
 
 return 0;   
}

[thetrojan01]

πφφφ με προλάβανε.

Όντως, μου φαίνεται Θ(n) για χρόνο και O(1) ή Ο(n) για μνήμη, εξαρτάται με την υλοποίηση του προγράμματος όσον αφορά τον πίνακα. Ο αλγόριθμος από μόνος του είναι Ο(1).
---------------
Επειδή βαριέμαι, παραθέτω τον ψευδοκώδικα του αλγορίθμου:

Κώδικας: Επιλογή όλων

// Looks if there are two elements of the array A, i and j,
// so that A[i] + A[j] = T; if found, returns true, else it returns false.

SUMCHECK(A, T)
    i <-- 1 
    j <-- A.length
    
    while(i < j)
        sum <-- A[i] + A[j]
        if(sum == T)
            return true
        elseif(sum > T)
            j = j - 1
        elseif(sum < T)
            i = i + 1
    return false

Απόδειξη ορθότητας του αλγορίθμου:
Αμετάβλητο βρόγχου: Στην αρχή κάθε επανάληψης του βρόγχου while θα έχουμε
A[k]+A[l] != T για κάθε k < i και l > j.

Initialization: Πριν την πρώτη επανάληψη το αμετάβλητο ισχύει, διότι δεν θα υπάρχει A[k] ή A[j] με k < i και l > j.
Maintenance: Το αμετάβλητο του βρόγχου διατηρείται σε κάθε επανάληψη, διότι διαφορετικά σε κάποια Ν-οστή επανάληψη θα υπήρχαν κάποια k < i και l > j έτσι ώστε A[k]+A[l]=T. Ωστόσο αν συνέβαινε αυτό, ο βρόγχος στην Μ < Ν επανάληψή του θα έδινε κάποια i και j έτσι ώστε A+A[j]=T, θα τερμάτιζε και το SUMCHECK θα επέστρεφε 'true'. Έτσι, δε θα υπήρχε N-οστή (μεταγενέστερη μιας M-οστής) επανάληψη του βρόγχου. Άτοπο.
--Όσο δε βρίσκονται i και j που να ικανοποιούν αυτό που ψάχνουμε, ο βρόγχος if, εφόσον ο πίνακας είναι ταξινομημένος, θα μας εγγυηθεί ότι θα προσεγγιστεί η λύση αφού:
------Αν το άθροισμα είναι μεγαλύτερο απ' αυτό που ψάχνουμε θα πρέπει ο μεγαλύτερος προσθετέος να μειωθεί. Άρα να μειωθεί το j.
------Αν το άθροισμα είναι μικρότερο απ' αυτό που ψάχνουμε θα πρέπει ο μικρότερος προσθετέος να αυξηθεί. Άρα να αυξηθεί το i.
Termination: Όταν ο βρόγχος while τερματίσει, θα υπάρχουν δύο περιπτώσεις:

1. Ότι τερμάτησε με i < j και επιστρέφει true. Ο βρόγχος if διαβεβαιώνει ότι θα έχουν βρεθεί i και j ώστε A + A[j] = T.
2. Ότι το i ταυτίστηκε με το j. Άρα δεν υπάρχουν i και j με i != j έτσι ώστε A+A[j]=T, μιας και έχουν ελεγχθεί όλα τα πιθανά k < i και l > j (βλ Maintenance)

Πρώτη φορά που αποδεικνύω αλγόριθμο... Αξιολογήστε την απόδειξή μου!

Τώρα για επίσημη απόδειξη πολυπλοκότητας μέσης περίπτωσης... δε θα το ψάξω καθόλου

[feedWARd]

@chris, @thetrojan01: Yeap, σωστοί και οι δύο. Αυτή είναι η καλύτερη λύση.

Την απόδειξη δεν την διάβασα, αλλά . Το CLRS είναι κακή επιρροή μερικές φορές

@pman: Επίσης σωστό, αλλά πιο αργό ( Ο(n^2) ).

[thetrojan01]

@chris, @thetrojan01: Yeap, σωστοί και οι δύο. Αυτή είναι η καλύτερη λύση.

Την απόδειξη δεν την διάβασα, αλλά . Το CLRS είναι κακή επιρροή μερικές φορές

@pman: Επίσης σωστό, αλλά πιο αργό ( Ο(n^2) ).

για μας του ΠΔΠ ναι, είναι κακή επιρροή... αλλά είναι τόσο ωραίο!

Λοιπόν, μόλις ξύπνησα είπα:

στο αμετάβλητο έπρεπε να λέω:
Αμετάβλητο βρόγχου: Στην αρχή κάθε επανάληψης του βρόγχου while θα έχουμε
A[k]+A[l] != T για κάθε k < i και/ή l > j.