Notasi Big O: Memahami Kerumitan Masa menggunakan Carta Aliran

Saya amat mengesyorkan siaran Edison tentang kerumitan Big-O dalam JavaScript. Ia adalah artikel paling mesra yang pernah saya lihat mengenai topik tersebut.

Artikel Tidak Tersedia Lagi

Saya akan mengambil mata daripada Edison di sini sambil saya menggambarkan kerumitan masa Big-O dengan carta alir.

O log(n)

Masa Logaritma

Cara saya memahami kerumitan masa secara visual ialah dengan melihat pada lelaran, i*2 sebagai contoh , dan melihat berapa banyak gelung fungsi itu.

O(n)

Masa Linear



Masa linear dan masa logaritma kelihatan serupa tetapi outputnya berbeza kerana keadaan gelung. exampleLogaritma(100) akan mengembalikan 1, 2, 4, 8, 16, 32, 64, manakala exampleLinear(100) hanya menggelung melalui semua integer positif di bawah 100.

O(n^2)

Masa Kuadratik



Bilangan gelung bertepatan dengan eksponen yang n dinaikkan. Anda benar-benar dapat melihat fungsi bertambah besar apabila kerumitan masa meningkat.

O(n^3)

Masa Kubik



Ini bukan satu-satunya cara untuk memahami kerumitan masa, tetapi ia benar-benar membantu untuk benar-benar melihat fungsi berkembang lebih lama apabila kerumitan masa meningkat. Kadangkala kod ditulis dalam hitam dan putih

 blok tidak menyampaikan maksud kepada pelajar visual.


Sekarang mari kita buat kuiz. Apakah kerumitan masa fungsi ini?

Buat tekaan anda...





Ia linear! Saya boleh tahu kerana terdapat satu gelung dan lelaran tidak menyebabkan gelung melangkau mana-mana integer.

Apakah kerumitan masa bagi fungsi ini?





Jangan meragui diri sendiri. Walaupun ini sedikit berbeza daripada contoh pertama, ia mempunyai kerumitan masa linear.

Apakah kerumitan masa bagi fungsi ini?





Anda mungkin melihat corak di sini. Ia linear!
Sekarang, jika anda telah mengikuti aliran logik saya, ini mungkin soalan muslihat:




Saya mengatakan bahawa bilangan gelung menandakan eksponen n dinaikkan kepada. Jadi mengapa ini mempunyai kerumitan masa linear dan bukan kuadratik?

Ini akan mempunyai kerumitan masa kuadratik jika ia menunjukkan gelung for di dalam gelung untuk yang lain. Walau bagaimanapun, satu untuk gelung yang berjalan selepas satu lagi untuk gelung tidak mempunyai kerumitan masa kuadratik melainkan linear.

Baiklah, jadi apakah kerumitan masa bagi fungsi ini?





Tiada apa-apa yang rumit di sini. Ini mempunyai kerumitan masa kuadratik.

Sekarang, untuk soalan terakhir anda - soalan yang mempersoalkan semua soalan lain - apakah kerumitan masa fungsi ini?





Saya harap anda melihat keadaan gelung for serta bilangan gelung yang banyak. Ini mempunyai kerumitan masa kuadratik kerana keadaan gelung i

Saya menjana imej dalam siaran ini dengan apl saya, yang proses pembangunannya saya terangkan dalam siaran lain:

[


  
  
  Bagaimana untuk mendapatkan 100 di Rumah Api



  
  
  ender minyard ・ Ogos 30 '20 ・ Bacaan 2 minit



  
  
  webperf#speed#javascript#webdev


](/ender_minyard/how-i-got-100-on-lighthouse-2icd)


          

            
        
Atas ialah kandungan terperinci Notasi Big O: Memahami Kerumitan Masa menggunakan Carta Aliran. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!