9
Jaki jest koszt/złożoność String.indexOf() wywołania funkcjiJaki jest koszt/złożoność rozmowy String.indexOf function()
A
Odpowiedz
0
w Javie, jeśli połączenie jest string1.indexOf (łańcuch2) koszt czasu będzie wynosił O (m - n), gdzie m jest długością ciągu1, a n jest długością łańcucha2. Realizacja
9
IIRC Java z .indexOf() jest tylko naive string matching algorithm, który jest O(n+m) średnie i O(n*m) najgorszy przypadek.
W praktyce jest to wystarczająco szybkie; Przetestowałem to na stosunkowo dużych igłach (> 500 znaków) i strunach siana (kilka MB), a dopasowywanie odbyłoby się poniżej sekundy (w przeciętnym komputerze domowym). Pamiętaj, że zmusiłem go do przejścia przez cały stóg siana.
+0
Wiem, że to dawno temu, ale czy wiesz skąd to masz? Potrzebuję tych informacji do mojej pracy licencjackiej i nie wiem, czy Stackoverflow byłby dopuszczalnym odniesieniem do pracy magisterskiej;) – odaa
+0
@odaa Przeprowadziłem kilka eksperymentów i napisałem o tym artykuł, kiedy byłem na studiach. – NullUserException
+0
@NullUserException, dlaczego mówisz, że 'O (n + m)' jest przeciętnym przypadkiem? http://stackoverflow.com/a/12752295/632951 wydaje się zaprzeczać temu punktowi. – Pacerier
0
W zależności od implementacji.
Na przykład podczas wyszukiwania ciągu w dłuższym ciągu "algorytm Turbo Boyer-Moore zajmuje dodatkową stałą ilość miejsca, aby zakończyć wyszukiwanie w porównaniu 2n (w przeciwieństwie do 3n dla Boyer-Moore), gdzie n to liczba znaków w wyszukiwanym tekście. " (patrz Wikipedia).
+1
@caleb: Naprawdę, jak możesz powiedzieć od pytania? –
Powiązane problemy
- 1. JQuery - Jaki jest cel tej składni $ (function() {...});
- 2. Dlaczego parametr string.indexOf jest int w Java
- 3. Dlaczego mój string.indexof (char) jest szybszy?
- 4. Funkcja String.indexOf w C
- 5. Jaki jest tego cel? (function ($) {// kod funkcji tutaj}) (jQuery);
- 6. string.IndexOf wyszukiwanie całego słowa meczu
- 7. Wydajność String.indexOf OrdinalIgnoreCase vs CurrentCultureIgnoreCase
- 8. Jaka jest różnica między on ("click", function()) i onclick = "function();"?
- 9. Jaka jest różnica pomiędzy $ (document) .ready (function() i $ (function()
- 10. Drzewo wyrażeń dla metody String.IndexOf
- 11. Dlaczego metoda String.indexOf nie jest częścią interfejsu CharSequence?
- 12. Skype URI rozmowy wideo
- 13. Jednoczesne połączenie do rozmowy
- 14. Konwertowanie funkcji boost :: function na std :: function
- 15. Metoda wyrażenie nie jest typu Function
- 16. Przestarzałe: Function eregi() jest przestarzałe w
- 17. `as.na` function
- 18. Co znaczy składnia! Function() {...}?
- 19. PHP call_user_func wiążą thisArg jak Javascript rozmowy
- 20. Boty telegramów: możliwe tajne rozmowy?
- 21. function()() in javascript
- 22. array_walk anonymous function
- 23. Python Function Return Loop
- 24. Tłumienie wyjścia w python subprocess rozmowy
- 25. liczyć najwyżej nie rozmowy między dwoma klientami
- 26. JavaScript URL Decode function
- 27. C# Variable = new function() {};
- 28. djb2 Hash Function
- 29. jQuery $ (function() {inicjalizacji
- 30. Javascript toFixed function
W jakim języku iw porównaniu do czego? Jakie są argumenty funkcji - czy bierze ciąg znaków, znak, niestandardowy porównujący? – Kobi
Czy mówisz o Javie? – NullUserException
duplikat http://stackoverflow.com/questions/12752274/java-indexofstring-str-method-complexity –