[teor. podst. inf.]złożoność obliczeniowa

Witam!
mam takie 3 algorytmy:

//Deklaracja funkcji INSERT
TREE insert(ETYPE x, TREE T)
{
	if (T == NULL)
{
		T = (TREE) malloc(sizeof(struct NODE));
		T->element = x;
	T->left = NULL;
		T->right = NULL;
}
else if (x < T->element)
		T->left = insert(x, T->left);
else if (x > T->element)
		T->right = insert(x, T->right);
return T;
}

//Deklaracja funkcji DELETE_TREE
TREE delete_tree(TREE T, ETYPE del, int lvl)
{
if(!T) return 0;
if (T->element!=del)  
root2 = insert(T->element, root2);
delete_tree(T->left, lvl+1, del);
delete_tree(T->right, lvl+1, del);  
return root2;

//Deklaracja funkcji FIND_TREE
int find(TREE T, ETYPE c, int LVL)
{
 	if (T==NULL)
      	return FALSE;
    	else
    		{
      		if (T->element==c)
        		return LVL;
      		if (T->element < c)
        		return find(T->right,c,LVL+1);
      		if (T->element > c)
        		return find(T->left,c,LVL+1);  
    		}      
} 

Dla każdego z nich musze obliczyć złożoność w ort!, najgorszym i średnim przypadku.
będe wdzięczny za wszelką pomoc, wskazówke, punkt zaczepienia...
Pozdrawiam

1. wyglada na logn gdzie n to wysokosc drzewa martwi mnie tylko to co sie stanie gdy napotka na pusty wskaznik w wezlie drzewa, w najlepszym przypadku bedzie O(1) w najgorszym O(n) gdzie n to ilosc lisci w drzewie (bo to jest zwykle binarne a wiec w najgorsyzm zamieni sie w liste) sredni przypadek powinien byc w okolicach O(logn)

2. usuniencie drzewa to zawsze O(n), masz tam insert wiec w najgorszym przypadku wstawienie nowego elementu zajmie O(n), tak wiec w najlepszym razie O(1), sredni O(n + logn), najgorszy O(2n)

3. typowe szukanie, w najlepszym O(1) w srednim cos kolo O(logn) w najgorszym O(n)

logn -> log o podsatwie 2

Cześć!
ja wiem ile wynosi złożoność w poszczególnych przypadkach, tylko cały ort! jest taki że nie mam pojęcia jak ją obliczyć

Jest to pesymistyczna (najczęściej, tudzież średnia) ilość wywołań funkcji/przebiegów pętli. Przy drzewach można narysować je sobie i pojeździć palcem po nim, symulując sobie działanie. Przy każdym zjeździe do dziecka w drzewie, zostawiasz za sobą ok. połowę elementów, które masz jeszcze do przeanalizowania, stąd log o podstawie 2.

W jaki sposób złozonośc w średnim przypadku algorytmu wstawiania elementu do drzewa wynosi logartym przy podstawie 2 z n? przecież ten algorytm to tylko 2 instrucje if, z których zawsze wykona sie tylko jedna zależnie od elementu jaki chcemy wrzyucić do drzewa. Przecież nie ma tam żadnych instrukcji typu for itp...

maverick84 napisał(a)

W jaki sposób złozonośc w średnim przypadku algorytmu wstawiania elementu do drzewa wynosi logartym przy podstawie 2 z n? przecież ten algorytm to tylko 2 instrucje if, z których zawsze wykona sie tylko jedna zależnie od elementu jaki chcemy wrzyucić do drzewa. Przecież nie ma tam żadnych instrukcji typu for itp...

Pod itp kryje się też wywołanie funkcji. Przecież wewnątrz tych ifów masz wywołanie kolejne funkcji insert. Ta funkcja wywoła się do log n razy.

OK już jarze, ale jak ta złozonośc zapisac matematycznie - za pomoca sigm?