Mengapa kita perlu mengisih tiga teratas? Hanya buka tiga ruang pembolehubah baharu untuk menyimpan hasil perantaraan.
Kerumitan kaedah ini ialah O(nk), n ialah jumlah data, dan k ialah bilangan data yang akan diperolehi. Pengisihan ialah O(nlogn) sama ada pengisihan timbunan atau pengisihan pantas. Masih ada kelebihan apabila k lebih kecil daripada log(2, 10 ** 8) Jika terlalu besar, ia akan merosot kepada jenis sisipan.
Terdapat N (N>>10000) integer, cari nombor K teratas terbesar di antaranya. (Dipanggil masalah algoritma Top k). Disebabkan oleh (1) sejumlah besar data input; (2) hanya K pertama, adalah agak tidak diingini untuk menyimpan dan mengisih keseluruhan data input. Masalah ini boleh dikendalikan menggunakan timbunan min struktur data.
Timbunan minimum, nilai setiap nod bukan daun mestilah tidak lebih besar daripada nilai nod anak. Dengan cara ini, timbunan minimum yang mengandungi nod K boleh digunakan untuk menyimpan nilai maksimum semasa K (sudah tentu nod akar adalah nilai minimum di antara mereka). Setiap kali terdapat input data, ia boleh dibandingkan dengan nod akar terlebih dahulu. Jika ia tidak lebih besar daripada nod akar, buang ia jika tidak, gantikan nilai nod akar dengan nilai baharu. Dan laraskan timbunan minimum.
Memandangkan hanya keping K data disimpan, kerumitan masa timbunan minimum dilaraskan kepada O(logK), jadi kerumitan masa bagi algoritma TOP K (masalah) ialah O(nlogK).
![[Web front-end] Permulaan pantas Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
Mengapa kita perlu mengisih tiga teratas? Hanya buka tiga ruang pembolehubah baharu untuk menyimpan hasil perantaraan.
Kerumitan kaedah ini ialah
O(nk), n ialah jumlah data, dan k ialah bilangan data yang akan diperolehi. Pengisihan ialahO(nlogn)sama ada pengisihan timbunan atau pengisihan pantas. Masih ada kelebihan apabila k lebih kecil daripadalog(2, 10 ** 8)Jika terlalu besar, ia akan merosot kepada jenis sisipan.Terdapat N (N>>10000) integer, cari nombor K teratas terbesar di antaranya. (Dipanggil masalah algoritma Top k). Disebabkan oleh (1) sejumlah besar data input; (2) hanya K pertama, adalah agak tidak diingini untuk menyimpan dan mengisih keseluruhan data input. Masalah ini boleh dikendalikan menggunakan timbunan min struktur data.
Timbunan minimum, nilai setiap nod bukan daun mestilah tidak lebih besar daripada nilai nod anak. Dengan cara ini, timbunan minimum yang mengandungi nod K boleh digunakan untuk menyimpan nilai maksimum semasa K (sudah tentu nod akar adalah nilai minimum di antara mereka). Setiap kali terdapat input data, ia boleh dibandingkan dengan nod akar terlebih dahulu. Jika ia tidak lebih besar daripada nod akar, buang ia jika tidak, gantikan nilai nod akar dengan nilai baharu. Dan laraskan timbunan minimum.
Memandangkan hanya keping K data disimpan, kerumitan masa timbunan minimum dilaraskan kepada O(logK), jadi kerumitan masa bagi algoritma TOP K (masalah) ialah O(nlogK).
Cukup cari
http://www.cnblogs.com/skywang12345/p/3610187.html
Untuk bukti dan terbitan, lihat Pengenalan kepada Algoritma
Tetapi anda tidak perlu mengumpulnya, lagipun, anda hanya mencari 3 nombor...
Bukankah ini soalan Top K biasa Anda boleh mencari Top K di Baidu
Jawapan topn betul jika bertindan Soalan diambil dari 3 ini. . . Jumlah yang begitu kecil
Ia adalah jenis timbunan
penyelesaian topk
Jika anda mahu menjadi terpantas, saya rasa pengisihan bitmap adalah yang terpantas pernah saya lihat.