@noobek101:
To ja się czuję wywołany do tablicy jako "znajomy z forum".
@Czulu:
Akurat tu patriarchat nie ma nic do rzeczy, historia jest bardzo ciekawa i pouczająca algorytmicznie:
Zacznijmy od początku: tu rzuciłem wskazówkę jak to trzeba zrobić Problem początkującego z binarnym drzewem... Taka moja uwaga na poczatek, że drzewa binarnego nie da sie inaczej zbudować, niż jako... drzewo binarne, więc o ile dobrze zrozumiałem, że connectis udzielił jej odpowiedzi, że jej drzewo binarne ma gorsza złożoność od ich wzorcowego rozwiązania (WTF?), to tu mi sie zapaliła pierwsza lampka ostrzegawcza. Kolejna lampka, że nie chciano jej udostępnić plików z danymi, na których to było testowane. No ok. skoro to taki rocket science, że nie może wyciec z centrali, to napisałem kilka linijek generujących takie pliki i jej udostępniłem. Noobek poprosiła, żebym porównał u siebie bo jej wychodzi że jej rozwiązanie działa ok. 10 razy ale szybciej. Odpaliłem i u mnie też jej wersja liczy szybciej, różnica tym wieksza im wieksza wysokość drzewa, przy wysokosci od korzenia do liscia 15, to bylo 0.76 s vs 2,19s, przy h=17: 1.6 s vs 11.6s na korzyść noobka. Potem nastąpił skokowy dramatyczny spadek wydajności tego algorytmu z connectis: 18: (2.3s vs 4m 45s), 19: (3.4s vs 17m 44s). Algo noobka dał jeszcze radę z h=20 w mniej niż 6 sek, tamtego drugiego nawet nie odpalałem. Zacząłem więc je porównywać i tak drzewo budują tak samo. Poruszaja się po drzewie w poszukiwaniu najstarszego wyrazu tak samo. Ale pan z connectis wspominał podobno coś o złożonościach, więc popatrzmy na różnicę, która jest w tym, że noobek po dojściu do liścia przy okazji łażenia po drzewie za każdym razem sprawdza czy utworzony wyraz jest najstarszy - musi przechowywać więc w pamieci jedną zmienną tekstową o dł. wysokości drzewa. Natomiast algo connectisa przy każdym dojsciu do liscia dodaje utworzone słowo do tablicy stringów, znaczy jeśli chodzi o ścisłość, to literalnie za każdym razem robi kopię poprzedniej tablicy z powiększoną o 1 długością i dopisuje do niej słowo. Po przejściu całego drzewa tablicę tę sortuje i zwraca ostatni wyraz. I w zasadzie na tym mógłbym skończyć tę opowieść. Aha zapomniałbym - z ciekawostek, to faktycznie rozwiązanie preferowane przez connectisa używa lomboka do węzłów drzewa.