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
Cara Menggunakan Python untuk Mencari Pengagihan Zipf Fail TeksCara Menggunakan Python untuk Mencari Pengagihan Zipf Fail TeksMar 05, 2025 am 09:58 AM

Tutorial ini menunjukkan cara menggunakan Python untuk memproses konsep statistik undang -undang ZIPF dan menunjukkan kecekapan membaca dan menyusun fail teks besar Python semasa memproses undang -undang. Anda mungkin tertanya -tanya apa maksud pengedaran ZIPF istilah. Untuk memahami istilah ini, kita perlu menentukan undang -undang Zipf. Jangan risau, saya akan cuba memudahkan arahan. Undang -undang Zipf Undang -undang Zipf hanya bermaksud: Dalam korpus bahasa semulajadi yang besar, kata -kata yang paling kerap berlaku muncul kira -kira dua kali lebih kerap sebagai kata -kata kerap kedua, tiga kali sebagai kata -kata kerap ketiga, empat kali sebagai kata -kata kerap keempat, dan sebagainya. Mari kita lihat contoh. Jika anda melihat corpus coklat dalam bahasa Inggeris Amerika, anda akan melihat bahawa perkataan yang paling kerap adalah "th

Cara memuat turun fail di pythonCara memuat turun fail di pythonMar 01, 2025 am 10:03 AM

Python menyediakan pelbagai cara untuk memuat turun fail dari Internet, yang boleh dimuat turun melalui HTTP menggunakan pakej Urllib atau Perpustakaan Permintaan. Tutorial ini akan menerangkan cara menggunakan perpustakaan ini untuk memuat turun fail dari URL dari Python. Permintaan Perpustakaan Permintaan adalah salah satu perpustakaan yang paling popular di Python. Ia membolehkan menghantar permintaan HTTP/1.1 tanpa menambahkan rentetan pertanyaan secara manual ke URL atau pengekodan data pos. Perpustakaan Permintaan boleh melaksanakan banyak fungsi, termasuk: Tambah data borang Tambah fail berbilang bahagian Akses data tindak balas python Buat permintaan kepala

Bagaimana saya menggunakan sup yang indah untuk menghuraikan html?Bagaimana saya menggunakan sup yang indah untuk menghuraikan html?Mar 10, 2025 pm 06:54 PM

Artikel ini menerangkan cara menggunakan sup yang indah, perpustakaan python, untuk menghuraikan html. Ia memperincikan kaedah biasa seperti mencari (), find_all (), pilih (), dan get_text () untuk pengekstrakan data, pengendalian struktur dan kesilapan HTML yang pelbagai, dan alternatif (sel

Penapisan gambar di pythonPenapisan gambar di pythonMar 03, 2025 am 09:44 AM

Berurusan dengan imej yang bising adalah masalah biasa, terutamanya dengan telefon bimbit atau foto kamera resolusi rendah. Tutorial ini meneroka teknik penapisan imej di Python menggunakan OpenCV untuk menangani isu ini. Penapisan Imej: Alat yang berkuasa Penapis Imej

Cara Bekerja Dengan Dokumen PDF Menggunakan PythonCara Bekerja Dengan Dokumen PDF Menggunakan PythonMar 02, 2025 am 09:54 AM

Fail PDF adalah popular untuk keserasian silang platform mereka, dengan kandungan dan susun atur yang konsisten merentasi sistem operasi, peranti membaca dan perisian. Walau bagaimanapun, tidak seperti Python memproses fail teks biasa, fail PDF adalah fail binari dengan struktur yang lebih kompleks dan mengandungi unsur -unsur seperti fon, warna, dan imej. Mujurlah, tidak sukar untuk memproses fail PDF dengan modul luaran Python. Artikel ini akan menggunakan modul PYPDF2 untuk menunjukkan cara membuka fail PDF, mencetak halaman, dan mengekstrak teks. Untuk penciptaan dan penyuntingan fail PDF, sila rujuk tutorial lain dari saya. Penyediaan Inti terletak pada menggunakan modul luaran PYPDF2. Pertama, pasangkannya menggunakan PIP: Pip adalah p

Cara Cache Menggunakan Redis dalam Aplikasi DjangoCara Cache Menggunakan Redis dalam Aplikasi DjangoMar 02, 2025 am 10:10 AM

Tutorial ini menunjukkan cara memanfaatkan caching redis untuk meningkatkan prestasi aplikasi python, khususnya dalam rangka kerja Django. Kami akan merangkumi pemasangan Redis, konfigurasi Django, dan perbandingan prestasi untuk menyerlahkan bene

Memperkenalkan Toolkit Bahasa Alam (NLTK)Memperkenalkan Toolkit Bahasa Alam (NLTK)Mar 01, 2025 am 10:05 AM

Pemprosesan bahasa semulajadi (NLP) adalah pemprosesan bahasa manusia secara automatik atau separa automatik. NLP berkait rapat dengan linguistik dan mempunyai hubungan dengan penyelidikan dalam sains kognitif, psikologi, fisiologi, dan matematik. Dalam sains komputer

Bagaimana untuk melakukan pembelajaran mendalam dengan Tensorflow atau Pytorch?Bagaimana untuk melakukan pembelajaran mendalam dengan Tensorflow atau Pytorch?Mar 10, 2025 pm 06:52 PM

Artikel ini membandingkan tensorflow dan pytorch untuk pembelajaran mendalam. Ia memperincikan langkah -langkah yang terlibat: penyediaan data, bangunan model, latihan, penilaian, dan penempatan. Perbezaan utama antara rangka kerja, terutamanya mengenai grap pengiraan

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

AI Hentai Generator

AI Hentai Generator

Menjana ai hentai secara percuma.

Alat panas

DVWA

DVWA

Damn Vulnerable Web App (DVWA) ialah aplikasi web PHP/MySQL yang sangat terdedah. Matlamat utamanya adalah untuk menjadi bantuan bagi profesional keselamatan untuk menguji kemahiran dan alatan mereka dalam persekitaran undang-undang, untuk membantu pembangun web lebih memahami proses mengamankan aplikasi web, dan untuk membantu guru/pelajar mengajar/belajar dalam persekitaran bilik darjah Aplikasi web keselamatan. Matlamat DVWA adalah untuk mempraktikkan beberapa kelemahan web yang paling biasa melalui antara muka yang mudah dan mudah, dengan pelbagai tahap kesukaran. Sila ambil perhatian bahawa perisian ini

Muat turun versi mac editor Atom

Muat turun versi mac editor Atom

Editor sumber terbuka yang paling popular

Dreamweaver Mac版

Dreamweaver Mac版

Alat pembangunan web visual

PhpStorm versi Mac

PhpStorm versi Mac

Alat pembangunan bersepadu PHP profesional terkini (2018.2.1).

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.