On Saturday, May 7, 2016 at 7:59:05 AM UTC+2, Borneq wrote:
> Ciągu root->syn->syn->syn..syn
> Chodzi o to że mam drzewo bloków Bitcoina. Blok jednego ma parenta i
> wektor dzieci, zwykle jedno dziecko, raz na jakiś czas dwa, może być
> więcej. Idziemy od roota - bloku 0. Tych bloków jest ponad 400 tysięcy.
> Co zrobić aby poziom rekursji nie był rzędu 400 tys, a co najwyżej 2-3 ?

Zapewne wiesz, jak wyszukać taki najdłuższy ciąg. O co naprawdę
pytasz? Jak to zrobić w najkrótszym czasie? Jeśli pytasz o
najkrótszy czas, to problem jest skomplikowany. Można
zapamiętać długość najdłuższego ciągu w każdym węźle. Niestety
przez to wstawianie i usuwanie będzie zajmowało nieco więcej
czasu, a drzewko zajmie nieco więcej pamięci. Czy się ogólnie
opłaca, zależy od rozkładu statystycznego operacji. Jeśli
mało modyfikujesz, jeśli drzewo jest duże, jeśli często
wyszukujesz najdłuższej ścieżki od roota do liścia, jeśli
masz zapas pamięci, to się będzie opłacało.

Swoją drogą, jak się mają bitcoiny? Idea bitcoinów rozwija
się czy upada?

Pozdrawiam