Struktury danych - jakiej użyć?

Odpowiedz Nowy wątek
2011-11-05 00:37
0

Witam. Zastanawia mnie jakiej struktury danych użyć, by w najefektywniejszy sposób móc przestawiać elementy jakiegoś zbioru. Np. mam ciąg znaków "GHIJ" i chcę sobie np. przestawić "I" na początek, dzięki czemu uzyskam "IGHJ". Do czegoś takiego najlepszym rozwiązaniem będzie lista dwukierunkowa czy może da się to wykonać jakoś lepiej?

Pozostało 580 znaków

2011-11-05 00:59
0

Zadanie Litery?

Nie ma takiej implementacji listy, która w czasie O(1) pozwoli na operacje "dodaj", "usuń", "przesuń" oraz "odczytaj pozycję".


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

2011-11-05 01:22
0

lista jest dobra do usuwania i przestawiania, aczkolwiek odległości między literami odczytasz tylko w czasie liniowym, próbuj dalej :P da się to zrobić w O(n log n) kombinując trochę, a jak nic nie wymyślisz to postaraj się zrobić jak najszybsze O(n^2)


░█░█░█░█░█░█░█░█░█░█░█░
edytowany 1x, ostatnio: krwq, 2011-11-05 01:22
nie należy podawać złożoności do zadań z OI! - Wibowit 2011-11-05 01:42
gdybym ja zawsze robił to co należy to za parę lat zostałbym papieżem :P nie grozi mi wywalenie, bo nie biorę w tym udziału :P złożoności praktycznie zawsze masz takie: n~1000: O(n<sup>2), n~10</sup>5: O(n log n) n~10^9: O(log n) lub O(1) - krwq 2011-11-05 01:53

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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