cari
Rumahpembangunan bahagian belakangTutorial PythonFaktor Kth bagi N - algoritma O(sqrt n).

pengenalan

Baru-baru ini saya menulis siaran Learn Big O Notation sekali dan untuk semua. Dalam catatan itu saya membincangkan semua jenis tatatanda masa Big O yang tersedia di lembaran cheat Big-O. Dan saya tidak fikir akan ada lagi notasi masa yang mungkin di luar tujuh itu.

Seolah-olah alam semesta itu sendiri merendahkan saya dan mengejek kejahilan saya, saya menghadapi masalah LeetCode dengan penyelesaian masa O(√n). Yang boleh diterjemahkan kepada O(N^1/2), jika anda gila.

Masalahnya

Anda diberi dua integer positif n dan k. Faktor bagi integer n ditakrifkan sebagai integer i dengan n % i == 0.

Pertimbangkan senarai semua faktor n yang diisih dalam tertib menaik, kembalikan faktor ke-k dalam senarai ini atau kembalikan -1 jika n mempunyai faktor kurang daripada k.

Penyelesaian yang jelas

Nah, jika anda seperti saya, fikiran pertama anda ialah meneliti setiap nombor dari 1 hingga n, periksa sama ada ia adalah faktor, dan jika ia berada dalam indeks k yang dikehendaki, kembalikannya.

Kodnya kelihatan seperti ini:

def getkthFactorOfN(n, k):
    result = 0
    for i in range(1, n + 1):
        if n % i == 0:
            result = result + 1
            if result == k:
                return i
    return -1

Ini semua baik dan menarik, tetapi ia "sahaja" O(n). Lagipun, hanya ada satu gelung dan ia naik ke n 1.
Setiap operasi lain dibuang apabila mempertimbangkan notasi masa.

Tetapi, kawan saya, ada tangkapan.

Memahami faktor

Jika anda memikirkannya, faktor "dicerminkan" selepas titik tertentu.

Ambil, sebagai contoh, nombor 81. Faktornya ialah [1, 3, 9, 27], di mana:

  • 1 * 81 = 81
  • 3 * 27 = 81
  • 9 * 9 = 81
  • 27 * 3 = 81
  • 81 * 1 = 81

Jika anda tidak mengira nombor 9, Operasi hanya diulang dan dibalikkan. Jika anda membahagikan n dengan salah satu faktornya, anda mendapat faktor lain.
Jangkakan punca kuasa dua bagi n, di mana ia adalah kuasa dua sendiri (duh).

Berbekalkan pengetahuan ini, kami kini tahu bahawa kami tidak perlu melelang melalui gelung sehingga n kali (dengan julat(1, n 1)), tetapi hanya sehingga math.sqrt(n). Selepas itu, kami mempunyai setiap faktor yang kami perlukan!

Penyelesaian yang tidak begitu jelas

Sekarang kita mempunyai semua yang kita perlukan, kita perlu mengubah gelung ini daripada 1 -> n hingga 1 -> persegi n.

Saya hanya akan membuang kod di sini dan kita akan pergi ke baris satu demi satu.

def getkthFactorOfN(n, k):
    i = 1
    factors_asc = []
    factors_desc = []
    while i * i 



<p>Oof, ia jauh lebih kompleks. Jom pecahkan:</p>

<p>Pertama, kita mulakan i = 1. Pembolehubah ini akan digunakan sebagai "nombor yang kita ada sekarang" semasa mencari faktor.</p>

<p>Kedua, kami akan mencipta dua tatasusunan: faktor_asc dan faktor_desc. Keajaiban di sini ialah kita akan menambah faktor pada factor_asc - ia dinamakan seperti ini kerana ia akan secara automatik dalam tertib menaik.<br>
Setiap kali kami menambahkan sesuatu pada factor_asc, kami akan membahagikan n dengannya dan menambahkannya pada faktor_desc. Logik yang sama di sini; ia akan ditambah dengan mudah dalam tertib menurun.</p><p>Kemudian, kita mulakan gelung kita. Di sini saya telah menukarnya menjadi semasa i * i 

</p><p>Kita mulakan dengan menyemak sama ada nombor semasa ialah faktor (n % i == 0). Jika ya, kami boleh menambahkannya pada tatasusunan factor_asc kami.</p>

<p>Seterusnya, kita mendapat "faktor songsang" i. Kita boleh melakukan ini dengan menyemak sama ada i != n // i, atau dengan kata lain, jika ia bukan punca. Ini kerana akar tidak boleh diduplikasi dalam kedua-dua tatasusunan. Jika tidak, kita mendapat faktor terbalik dengan menjalankan n // i dan menambahkan hasilnya dalam faktor_desc.</p>

<p>Selepas itu, kami menambah 1 pada i dan meneruskan gelung kami.</p>

<p>Selepas gelung selesai, kita mesti mempunyai setiap faktorial yang kita perlukan.</p>

<p>Kita mulakan dengan menyemak sama ada k berada pada separuh pertama termasuk punca (yang boleh ditafsirkan sebagai tengah) dengan jika k 

</p><p>Jika tidak, kita mesti menolak jumlah faktor yang ditemui daripada k dan semak semula - dengan k -= len(faktor_asc) dan jika k 

</p><p>Jika k berada di dalam faktor_desc, dapatkan nilainya dengan factor_desk[-k] (dari terakhir hingga pertama).</p>

<p>Jika semuanya gagal, kembalikan -1.</p>

<h2>
  
  
  Lengkung
</h2>

<p>Jika anda tertanya-tanya di mana dalam graf lengkung ia mendarat, ia akan berada di antara <strong>O(n)</strong> dan <strong>O(log n)</strong>, lebih baik daripada yang pertama dan lebih teruk daripada yang terakhir. Berikut ialah graf:</p>

<p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/173598658415895.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="The Kth factor of N - an O(sqrt n) algorithm"><br>
<em>Terdapat di Mathspace</em></p>

<h2>
  
  
  Kesimpulan
</h2>

<p>Ini adalah perjalanan untuk mendedahkan dan menyelidik. Terima kasih banyak kerana membaca sehingga ke tahap ini.</p>

<p>Jika anda ingin lebih dioptimumkan, anda boleh mencipta faktor_asc_len dan faktor_desc_len pembolehubah dan menambah 1 setiap kali anda menambahkan nilai pada tatasusunan ini, supaya kaedah len() tidak perlu dipanggil, kerana kaedah ini adalah <strong>O(n)</strong> supaya ia boleh memberi kesan kepada notasi masa.</p>

<p>Semoga berjaya dalam pelajaran anda dan sehingga kali seterusnya!</p>


          

            
        

Atas ialah kandungan terperinci Faktor Kth bagi N - algoritma O(sqrt n).. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Apakah penyataan suis python?Apakah penyataan suis python?Apr 30, 2025 pm 02:08 PM

Artikel ini membincangkan pernyataan baru "Match" Python yang diperkenalkan dalam versi 3.10, yang berfungsi sebagai setara dengan menukar pernyataan dalam bahasa lain. Ia meningkatkan kebolehbacaan kod dan menawarkan manfaat prestasi ke atas tradisional if-elif-el

Apakah kumpulan pengecualian dalam Python?Apakah kumpulan pengecualian dalam Python?Apr 30, 2025 pm 02:07 PM

Kumpulan Pengecualian dalam Python 3.11 Membenarkan mengendalikan pelbagai pengecualian secara serentak, meningkatkan pengurusan ralat dalam senario serentak dan operasi kompleks.

Apakah anotasi fungsi dalam python?Apakah anotasi fungsi dalam python?Apr 30, 2025 pm 02:06 PM

Fungsi anotasi dalam python Tambah metadata ke fungsi untuk pemeriksaan jenis, dokumentasi, dan sokongan IDE. Mereka meningkatkan kebolehbacaan kod, penyelenggaraan, dan penting dalam pembangunan API, sains data, dan penciptaan perpustakaan.

Apakah ujian unit di Python?Apakah ujian unit di Python?Apr 30, 2025 pm 02:05 PM

Artikel ini membincangkan ujian unit di Python, faedah mereka, dan bagaimana menulisnya dengan berkesan. Ia menyoroti alat seperti Unittest dan Pytest untuk ujian.

Apakah penentu akses dalam python?Apakah penentu akses dalam python?Apr 30, 2025 pm 02:03 PM

Artikel membincangkan penentu akses dalam Python, yang menggunakan konvensyen penamaan untuk menunjukkan keterlihatan ahli kelas, dan bukan penguatkuasaan yang ketat.

Apakah __init __ () dalam python dan bagaimana diri memainkan peranan di dalamnya?Apakah __init __ () dalam python dan bagaimana diri memainkan peranan di dalamnya?Apr 30, 2025 pm 02:02 PM

Artikel membincangkan kaedah Python \ _ _ _ _ _ \ _ () dan peranan diri dalam memulakan atribut objek. Kaedah kelas lain dan kesan warisan pada \ _ _ _ init \ _ \ _ () juga dilindungi.

Apakah perbezaan antara kaedah @classmethod, @staticmethod dan contoh dalam python?Apakah perbezaan antara kaedah @classmethod, @staticmethod dan contoh dalam python?Apr 30, 2025 pm 02:01 PM

Artikel ini membincangkan perbezaan antara @classmethod, @staticmethod, dan kaedah contoh dalam python, memperincikan sifat mereka, kes penggunaan, dan faedah. Ia menerangkan cara memilih jenis kaedah yang betul berdasarkan fungsi yang diperlukan dan da

Bagaimana anda menambah elemen ke array python?Bagaimana anda menambah elemen ke array python?Apr 30, 2025 am 12:19 AM

Inpython, youAppendElementStoalistusingTheAppend () method.1) useAppend () forsingLements: my_list.append (4) .2) useextend () or = formultipleelements: my_list.extend (lain_list) ormy_list = [4,5,6] .3) UseInsert () ForSpecificPositions: my_list.insert (1,5) .beaware

See all articles

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

Video Face Swap

Video Face Swap

Tukar muka dalam mana-mana video dengan mudah menggunakan alat tukar muka AI percuma kami!

Alat panas

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

Persekitaran pembangunan bersepadu PHP yang berkuasa

mPDF

mPDF

mPDF ialah perpustakaan PHP yang boleh menjana fail PDF daripada HTML yang dikodkan UTF-8. Pengarang asal, Ian Back, menulis mPDF untuk mengeluarkan fail PDF "dengan cepat" dari tapak webnya dan mengendalikan bahasa yang berbeza. Ia lebih perlahan dan menghasilkan fail yang lebih besar apabila menggunakan fon Unicode daripada skrip asal seperti HTML2FPDF, tetapi menyokong gaya CSS dsb. dan mempunyai banyak peningkatan. Menyokong hampir semua bahasa, termasuk RTL (Arab dan Ibrani) dan CJK (Cina, Jepun dan Korea). Menyokong elemen peringkat blok bersarang (seperti P, DIV),

SecLists

SecLists

SecLists ialah rakan penguji keselamatan muktamad. Ia ialah koleksi pelbagai jenis senarai yang kerap digunakan semasa penilaian keselamatan, semuanya di satu tempat. SecLists membantu menjadikan ujian keselamatan lebih cekap dan produktif dengan menyediakan semua senarai yang mungkin diperlukan oleh penguji keselamatan dengan mudah. Jenis senarai termasuk nama pengguna, kata laluan, URL, muatan kabur, corak data sensitif, cangkerang web dan banyak lagi. Penguji hanya boleh menarik repositori ini ke mesin ujian baharu dan dia akan mempunyai akses kepada setiap jenis senarai yang dia perlukan.

Penyesuai Pelayan SAP NetWeaver untuk Eclipse

Penyesuai Pelayan SAP NetWeaver untuk Eclipse

Integrasikan Eclipse dengan pelayan aplikasi SAP NetWeaver.

MinGW - GNU Minimalis untuk Windows

MinGW - GNU Minimalis untuk Windows

Projek ini dalam proses untuk dipindahkan ke osdn.net/projects/mingw, anda boleh terus mengikuti kami di sana. MinGW: Port Windows asli bagi GNU Compiler Collection (GCC), perpustakaan import yang boleh diedarkan secara bebas dan fail pengepala untuk membina aplikasi Windows asli termasuk sambungan kepada masa jalan MSVC untuk menyokong fungsi C99. Semua perisian MinGW boleh dijalankan pada platform Windows 64-bit.