zlozonosc algoytmu wyszukiwania

0

w jakich przypadkach zlozonosc funkcji search() jest lepsza niz O(n)

# include <iostream>
using namespace std;

struct range;

struct range {
    double begin;
    double end;
    range *left;
    range *right;
    
    range (double a, double b) {
              begin = a;
              end = b;
              left = NULL;
              right = NULL;
    }
};

range *rangePointer;

bool add (double a, double b, range *&r = rangePointer) {
     
    if (r == NULL) {
        r = new range( a, b );
        return true;
    }
    if (r->begin > b) {
        return add( a, b, r->left );
    }
    if (r->end < a) {
        return add( a, b, r->right );
    }
    return false;
}

void search (double f, range *&r = rangePointer) {
     
    if (r == NULL) {
       cout << "liczba " << f << " nie nalezy do zadnego z przedzialow" << endl;
       return;
    }
    if (r->begin > f) {
        return search(f, r->left);
    }
    if (r->end < f) {
        return search(f, r->right);
    }
    cout << "liczba " << f << " nalezy do ( " << r->begin << ", " << r->end << " )" << endl;
    return;
}

int main () {
    
    bool odp = true;
    int rep = 0;
    double begin = 0, end = 0, number = 0;
    
    while (odp) {
         printf("\n\nPodaj: ");
         printf("\n1) aby dodac nowy przydzial");
         printf("\n2) aby wyszukac liczbe w przedziale");
         printf("\n3) aby zakonczyc program\n");
         scanf("%d",&rep);
         
         switch (rep) {
                case 1:
                     printf("\nPodaj odpowiednio poczatek i koniec przedzialu: \n");
                     scanf("%d",&begin);scanf("%d",&end);
                     add(begin,end);
                     break;
                case 2:
                     printf("\nPodaj liczbe aby wyszukac przedzial w ktorym sie znajduje: ");
                     scanf("%d",&number);
                     search(number);
                     break;
                case 3:
                     odp = false;
         }
    }
    
    system("pause");
    return 0;
}
0

jeżeli długość ścieżki do końcowego przedziału (tzn. takiego w którym zawiera się podana liczba, albo, jeżeli liczba nie zostanie znaleziona, ostatniego sprawdzonego przedziału) jest (asymptotycznie) mniejsza od o(n).

złożoność pesymistyczna dowolnej wyszukiwania jest mniejsza od o(n) jeżeli wysokość drzewa przedziałowego jest mniejsza (asymptotycznie) od o(n).

złożoność zamortyzowana ciągu operacji wyszukiwania jest mniejsza od n * o(n) jeżeli średnia wartość ciągu długości przeszukiwanych ścieżek jest (asymptotycznie) mniejsza od o(n).

1 użytkowników online, w tym zalogowanych: 0, gości: 1