Panduan Ringkas 10^8

Pengadil dalam talian biasa menjalankan kira-kira 10^8 operasi mudah sesaat. Nombor itu ialah bajet yang boleh digunakan oleh keseluruhan program Anda. 💡

Darabkan jumlah operasi dengan kerja bagi setiap langkah, kemudian bandingkan dengan had masa. Jika jumlah langkah masih dalam bajet, penyelesaian Anda berkemungkinan lulus.

Imbasan O(n) untuk n = 10^6 hanya memerlukan sejuta langkah, jauh di bawah bajet. Penyelesaian linear hampir sentiasa lulus dengan selesa.

Untuk n = 10^6, pengisihan O(n log n) memerlukan kira-kira 2 kali 10^7 langkah. Ia masih jauh dalam bajet satu saat, jadi pengisihan jarang menjadi titik kesesakan.

Pendekatan O(n^2) mencapai bajet sekitar n = 10^4, apabila kosnya ialah 10^8 langkah. Selepas itu, kaedah kuadratik mula melebihi had masa.

Penyelesaian O(n^3) hanya bertahan sehingga kira-kira n = 500. Kuasakan tiga nilai itu dan Anda mendapat kira-kira 10^8 langkah, iaitu had bajet.

O(2^n) berganda pada setiap langkah, jadi ia hanya berfungsi untuk n yang sangat kecil, sekitar 20 hingga 25. Selepas itu, jumlah operasi melonjak melebihi 10^8.

Python lebih perlahan bagi setiap langkah, jadi anggap bajet lebih hampir kepada 10^7 untuk gelung yang ketat. Bersikap konservatif apabila kekangan kelihatan hampir kepada had.

Peraturan 10^8 mengira langkah mudah. Kerja berat di dalam gelung, seperti membina rentetan, menambah faktor pemalar yang mengecilkan bajet sebenar Anda.

Had masa selalunya ialah 1 atau 2 saat. Had 2 saat secara kasar menggandakan bajet Anda dan memberikan sedikit ruang tambahan.

Sentiasa masukkan n ke dalam kerumitan Anda dan bandingkan dengan 10^8 terlebih dahulu. Semakan kewajaran pantas ini mengelakkan Anda daripada menulis penyelesaian yang pasti gagal.

Anda kini boleh memetakan operasi kepada masa: kira-kira 10^8 sesaat. Kerumitan linear dan n log n selamat, kuadratik terhad sekitar 10^4, dan Anda membuat semakan sebelum menulis kod. ✅