Potrzebuję potwierdzenia na coś naprawdę szybko. Jeśli testowanie algorytmu trwa od n(n-1)/2
, to czy jest to wielki numer O(n^2)
?Big Oh notation
10
A
Odpowiedz
15
n (n-1)/2 rozszerza się (n^2 -n)/2
, czyli (n^2/2) - (n/2)
(n^2/2)
i (n/2)
są dwa składniki funkcji, z których dominuje n^2/2
. Dlatego możemy zignorować część - (n/2)
.
Od n^2/2
można bezpiecznie usunąć część/2 w asymptotycznej analizie notacji.
Upraszcza do n^2
Dlatego tak, to jest w czasie O (n^2)
5
Tak, zgadza się.
n(n-1)/2
rozszerza się n^2/2 - n/2
:
Określenie liniowy n/2
spada ponieważ jest niższego rzędu. Pozostawia to n^2/2
. Stała zostaje wchłonięta przez big-O, pozostawiając n^2
.
3
Tak:
n(n-1)/2 = (n2-n)/2 = O(n^2)
2
Tak, to prawda. n(n-1)/2
jest (n^2 - n)/2
, która jest wyraźnie mniejsza niż c*n^2
dla wszystkich n>=1
jeśli wybrać c
to przynajmniej 1.
Powiązane problemy
- 1. Big Oh Notation - definicja formalna
- 2. Big Oh for (n log n)
- 3. Potrzebuję pomocy w zrozumieniu, jak znaleźć Big-Oh segmentu kodu
- 4. Big-Oh Wydajność sprzężenie wewnętrzne na dwa wskaźniki
- 5. Czy ktoś mógłby wytłumaczyć Big O kontra Big Omega vs Big Theta?
- 6. jQuery Object array notation
- 7. Dlaczego ten kod jest uważany za O (N^6) w notacji Big Oh?
- 8. Analiza Big-O dla pętli
- 9. Reading Scientific Notation w C
- 10. C# notation understanding Select (int.Parse)
- 11. Eliksir: pisanie sparametryzowanej funkcji za pomocą & Notation
- 12. konfiguracja Proguard Big zapytania
- 13. Big Merge/Zarządzanie pamięcią
- 14. Little/Big Endian
- 15. Big O metod rekursywnych
- 16. Big O - zagnieżdżone pętle
- 17. Problemy z odinstalowaniem oh-my-zsh?
- 18. Instalacja oh-my-zsh zwraca kod niezerowy
- 19. Jak udowodnić relacje big-o
- 20. Analiza dwóch algorytmów Big-O
- 21. PostgreSQL Big Text Column Performance
- 22. Little endian Vs Big endian
- 23. Powiadomienie Big Text Android GCM
- 24. Big-O z wycięciem listy
- 25. Węzeł.JS Big-Endian UCS-2
- 26. Git big commit best practices
- 27. Big Text Corpus Breaks tm_map
- 28. Confused o Big O notacji
- 29. Jackson: Konwersja własność JSON do obiektu zagnieżdżonego z Dot Notation
- 30. Mrówka, pliki JAR i Ścieżka Klasy oh my
Dzięki za pomoc! – Jay
@Jeśli powinieneś zaakceptować odpowiedź, jeśli uważasz, że spełnia twoje pytanie – dgraziotin