Algoritma: Bagaimana cara saya menjumlahkan O (n) dan O (nlog (n)) bersamaan?

22

Saya memiliki algoritma ikuti yang menemukan duplikat dan menghapusnya:

public static int numDuplicatesB(int[] arr) {
    Sort.mergesort(arr);
    int numDups = 0;
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] == arr[i - 1]) {
            numDups++;
} }
    return numDups;
}

Saya mencoba untuk menemukan kompleksitas waktu kasus terburuk ini. Saya tahu mergesort adalah nlog(n), dan dalam loop saya, saya mengulangi seluruh set data sehingga akan dihitung sebagai n. Saya tidak yakin apa yang harus dilakukan dengan angka-angka ini. Haruskah saya menjumlahkannya bersama? Jika saya melakukan itu, bagaimana saya melakukannya?

algorithms algorithm-analysis big-o chopper draw lion4
sumber
1
Catatan: Anda bisa menggunakan tabel hash untuk melakukan ini di O (n) tergantung pada kebutuhan memori.
corsiKa

Jawaban:

67 
O(n) + O(n log(n)) = O(n log(n))

Untuk kompleksitas O Besar, semua yang Anda pedulikan adalah istilah dominan. n log(n)mendominasi nsehingga itulah satu-satunya istilah yang Anda pedulikan.

Gua Justin
sumber
4
Cara lain untuk berpikir tentang ini adalah dengan membayangkan pemrosesan O (n) Anda benar-benar O (n log n), seolah-olah Anda melakukan dua macam independen. Maka Anda akan memiliki 2 * O (n log n). Tetapi konstanta terlepas, jadi Anda kembali ke O (n log n).
Jonathan Eunice
4
@ Jonathan Sementara itu bekerja dalam prakteknya, sangat benar bahwa O (n) tidak sama dengan O (n log (n)), jadi saya tidak akan menyarankan untuk menggunakannya secara teratur.
Aza
17
@Emrakul sebenarnya saya pikir alasannya secara teori juga praktis. O (n) adalah subset O (n log (n)) yang tepat. Jadi, jika f (n) milik O (n) juga milik O (n log (n)).
emory
17
Perlu dicatat bahwa ketika kita mengatakan f(n) is O(g(n))apa yang sebenarnya kita katakan adalah fungsinya f is a member of the set of functions that grows at the rate of at most g(n) over the long term. Ini berarti semua anggota O(n)juga anggota O(n*log(n)). The +dalam ekspresi suka O(f(n)) + O(g(n))sebenarnya merujuk ke set union (yang dari Anda benar-benar bertele-tele, Anda benar-benar harus menggunakan ∪).
Lie Ryan
3
@LieRyan Awalnya, itu tidak diatur serikat, tapi set sum: A + B = { a + b | a in A, b in B }. Itu terjadi bahwa untuk set formulir O(g(n))ini sama dengan set union, karena salah satu set selalu merupakan subset dari yang lain, dan mereka berdua tidak sama dengan jumlah (yaitu A + A = A). (Ups, Nate memang menulis dasarnya sama).
Paŭlo Ebermann
56

Mari kita pikirkan jalan kita melaluinya dan ingat definisi O. Yang akan saya gunakan adalah untuk batas tak terbatas.

Anda benar dalam menyatakan bahwa Anda melakukan dua operasi dengan batas asimtotik yang sesuai O(n)dan O(nlog(n))tetapi menggabungkannya ke dalam satu ikatan tidak sesederhana menambahkan kedua fungsi tersebut. Anda tahu fungsi Anda membutuhkan setidaknya O(n)waktu dan juga setidaknya O(nlog(n))waktu. Jadi sebenarnya kelas kompleksitas untuk fungsi Anda adalah penyatuan O(n)dan O(nlog(n))tetapi O(nlog(n))merupakan superset dari O(n)begitu benar-benar adil O(nlog(n)).

davidk01
sumber
12
+1 ini harus menjadi jawabannya. Ini menjelaskan jawaban lebih tepatnya menggunakan istilah compsci.
5

Jika Anda akan menetapkannya dengan tangan itu akan terlihat kira-kira seperti ini:

Misalkan total waktu adalah: log + bn (n), di mana a dan b adalah konstanta (mengabaikan syarat urutan lebih rendah).

Saat n menuju tak terhingga (log + bn (n)) / n log (n) -> a / log (n) + b -> b

Jadi total waktu adalah O (bn log (n)) = O (n log (n)).

richardb
sumber
2

Mulai dengan definisi O ():

O (n log n) berarti "kurang dari C n log n, jika n besar".

O (n) berarti "kurang dari D n, jika n besar".

Jika Anda menambahkan keduanya, hasilnya kurang dari C n log n + D n <C n log n + D n log n <(C + D) n log n = O (n log n).

Secara umum, jika f (n)> Cg (n) untuk n besar dan beberapa C> 0, maka O (f (n)) + O (g (n)) = O (f (n)). Dan setelah melakukan beberapa kasus menggunakan definisi O (), Anda akan tahu apa yang bisa dan tidak bisa Anda lakukan.

gnasher729
sumber
1

Notasi O besar didefinisikan sebagai satu set:

masukkan deskripsi gambar di sini

Jadi masukkan deskripsi gambar di siniberisi semua fungsi yang - mulai dari titik besar sembarangmasukkan deskripsi gambar di sini - selalu lebih kecil dari g.

Sekarang, ketika Anda memiliki fungsi yang ada di dalam masukkan deskripsi gambar di sinidan kemudian jalankan fungsi lain yang meningkatkan lebih lambat daripada g itu tentu saja meningkat lebih lambat dari 2g. Jadi mengeksekusi sesuatu yang lebih lambat daripada g tidak akan mengubah kelas kompleksitas.

Lebih formal:

f, h \ in \ mathcal {O} (g) \ Rightarrow (f + h) \ in \ mathcal {O} (g)

Anda dapat dengan mudah membuktikannya.

TL; DR

Ini masih n log (n)

Martin Thoma
sumber