Mari permudahkan kerumitan algoritma!

Sudah lama saya mula berfikir untuk kembali ke asas dan memanfaatkan konsep sains komputer teras. Dan saya fikir, sebelum melompat ke kumpulan topik kelas berat seperti struktur data, sistem operasi, OOP, pangkalan data, dan reka bentuk sistem (serius, senarai itu tidak berkesudahan) ?, Saya mungkin harus mengambil topik yang kita semua tidak mahu sentuhan: Analisis Kerumitan algoritma.

Yap! Konsep yang sering diketepikan, kerana sebilangan besar pemaju kita berfikir, "Hmm, saya mungkin tidak perlu mengetahuinya sedangkan saya sebenarnya membuat kod!".?

Saya tidak pasti sama ada anda perlu memahami bagaimana analisis algoritma berfungsi. Tetapi jika anda berjaya, inilah percubaan saya untuk menerangkannya dengan cara yang paling jelas. Saya harap ia dapat membantu orang seperti saya.?

Apa itu analisis algoritma, dan mengapa kita memerlukannya? ?

Sebelum menyelami analisis kerumitan algoritma, mari kita dapatkan idea ringkas mengenai analisis algoritma. Analisis algoritma berkaitan dengan membandingkan algoritma berdasarkan jumlah sumber pengkomputeran yang digunakan setiap algoritma.

Apa yang ingin kita capai dengan amalan ini ialah dapat membuat keputusan yang tepat mengenai algoritma mana yang menjadi pemenang dari segi penggunaan sumber yang cekap (masa atau memori, bergantung pada kes penggunaan). Adakah ini masuk akal?

Mari kita ambil contoh. Katakan kita mempunyai produk fungsi () yang menggandakan semua elemen array, kecuali elemen pada indeks semasa, dan mengembalikan array baru. Sekiranya saya memberikan [1,2,3,4,5] sebagai input, saya akan mendapat [120, 60, 40, 30, 24] sebagai hasilnya.

Fungsi di atas menggunakan dua bersarang untuk gelung untuk mengira hasil yang diinginkan. Pada hantaran pertama, ia mengambil elemen pada kedudukan semasa. Pada hantaran kedua, ia mengalikan elemen itu dengan setiap elemen dalam larik - kecuali apabila unsur gelung pertama sepadan dengan elemen gelung kedua semasa. Dalam kes itu, ia hanya menggandakannya dengan 1 untuk memastikan produk tidak diubah suai.

Adakah anda boleh mengikuti? Hebat!

Ini adalah pendekatan sederhana yang berfungsi dengan baik, tetapi dapatkah kita membuatnya lebih baik? Bolehkah kita mengubahnya sedemikian rupa sehingga kita tidak perlu menggunakan dua gelung bersarang? Mungkin menyimpan hasil pada setiap hantaran dan memanfaatkannya?

Mari pertimbangkan kaedah berikut. Dalam versi yang diubah suai ini, prinsip yang diterapkan adalah untuk setiap elemen, hitung produk nilai di sebelah kanan, hitung produk nilai di sebelah kiri, dan gandakan dua nilai tersebut. Cukup manis, bukan?

Di sini, daripada menggunakan gelung bersarang untuk mengira nilai pada setiap larian, kami menggunakan dua gelung tidak bersarang, yang mengurangkan kerumitan keseluruhan dengan faktor O (n) (kita akan sampai kemudian).

Kita dapat membuat kesimpulan bahawa algoritma terakhir berprestasi lebih baik daripada yang sebelumnya. Setakat ini, bagus? Sempurna!

Pada ketika ini, kita juga dapat melihat dengan cepat pelbagai jenis analisis algoritma yang ada di luar sana. Kami tidak perlu melihat perincian tahap minit, tetapi hanya perlu mempunyai pemahaman asas mengenai jargon teknikal.

Bergantung pada kapan algoritma dianalisis, iaitu sebelum pelaksanaan atau setelah pelaksanaan, analisis algoritma dapat dibagi menjadi dua tahap:

  • Analisis Apriori - Seperti namanya, pada apriori (sebelumnya), kami melakukan analisis (ruang dan waktu) algoritma sebelum menjalankannya pada sistem tertentu. Jadi pada asasnya, ini adalah analisis teori algoritma. Kecekapan algoritma diukur dengan anggapan bahawa semua faktor lain, misalnya, kelajuan pemproses, adalah tetap dan tidak mempengaruhi pelaksanaannya.
  • Analisis Apostiari - Analisis Apostiari algoritma dilakukan hanya setelah menjalankannya pada sistem fizikal. Algoritma yang dipilih dilaksanakan menggunakan bahasa pengaturcaraan yang dijalankan pada mesin komputer sasaran. Ia secara langsung bergantung pada konfigurasi sistem dan perubahan dari sistem ke sistem.

Di industri ini, kami jarang melakukan analisis Apostiari, kerana perisian umumnya dibuat untuk pengguna tanpa nama yang mungkin menjalankannya pada sistem yang berbeza.

Oleh kerana kerumitan masa dan ruang dapat berbeza dari satu sistem ke sistem yang lain, Analisis Apriori adalah kaedah yang paling praktikal untuk mencari kerumitan algoritma. Ini kerana kita hanya melihat variasi asimptotik (kita akan sampai kemudian) algoritma, yang memberikan kerumitan berdasarkan ukuran input dan bukannya konfigurasi sistem.

Setelah kita memahami asas analisis algoritma, kita dapat meneruskan topik utama kita: kerumitan algoritma. Kami akan memfokuskan pada Analisis Apriori , dengan mempertimbangkan skop siaran ini, jadi mari kita mulakan.

Selami kerumitan dengan analisis asimtotik

Analisis kerumitan algoritma adalah alat yang membolehkan kita menjelaskan bagaimana algoritma berkelakuan ketika input bertambah besar.

Oleh itu, jika anda ingin menjalankan algoritma dengan kumpulan data ukuran n , misalnya, kita dapat menentukan kerumitan sebagai fungsi berangka f (n) - masa berbanding ukuran input n .

Sekarang anda pasti tertanya-tanya, tidak mungkin algoritma mengambil masa yang berlainan pada input yang sama, bergantung pada faktor seperti kelajuan pemproses, set arahan, kelajuan cakera, dan jenama penyusunnya? Jika ya, maka tepuk punggung, kerana anda betul !?

Di sinilah Analisis Asimptotik masuk ke dalam gambar ini. Di sini, konsepnya adalah untuk menilai prestasi algoritma dari segi ukuran input (tanpa mengukur masa sebenar yang diperlukan untuk dijalankan). Oleh itu, pada asasnya, kita mengira bagaimana masa (atau ruang) yang diambil oleh algoritma meningkat ketika kita membuat ukuran input sangat besar.

Analisis kerumitan dilakukan pada dua parameter:

  1. Masa : Kerumitan masa memberi petunjuk berapa lama algoritma diperlukan untuk menyelesaikan berkenaan dengan ukuran input. Sumber yang menjadi perhatian kami dalam kes ini adalah CPU (dan waktu jam dinding).
  2. Ruang : Kerumitan ruang serupa, tetapi merupakan indikasi berapa banyak memori yang "diperlukan" untuk menjalankan algoritma berkenaan dengan ukuran input. Di sini, kita menangani RAM sistem sebagai sumber.

Adakah awak masih bersama saya? Baik! Sekarang, terdapat notasi berbeza yang kita gunakan untuk menganalisis kerumitan melalui analisis asimptotik. Kami akan membahas semuanya satu persatu dan memahami asas-asas di sebalik masing-masing.

The Big oh (Big O)

Notasi pertama dan paling popular yang digunakan untuk analisis kerumitan adalah notasi BigO. Sebabnya adalah kerana ia memberikan analisis terburuk bagi algoritma. Alam semesta kutu buku kebanyakannya bimbang tentang seberapa buruk algoritma dapat bertindak, dan bagaimana ia dapat dibuat agar berprestasi lebih baik. BigO memberikan kita tepat.

Mari masuk ke bahagian matematik untuk memahami perkara-perkara yang menjadi intinya.

Mari pertimbangkan algoritma yang dapat dijelaskan oleh fungsi f (n). Jadi, untuk menentukan BigO dari f (n) , kita perlu mencari fungsi, katakanlah, g (n) , yang membataskannya. Maknanya, setelah nilai tertentu, n0, nilai g (n) akan selalu melebihi f (n) .

Kita boleh menulisnya sebagai,

f (n) ≤ C g (n)

di mana n≥n0; C> 0; n0≥1

If above conditions are fulfilled, we can say that g(n) is the BigO of f(n), or

f(n) = O (g(n))

Can we apply the same to analyze an algorithm? This basically means that in worst case scenario of running an algorithm, the value should not pass beyond a certain point, which is g(n) in this case. Hence, g(n) is the BigO of f(n).

Let’s go through some commonly used bigO notations and their complexity and understand them a little better.

  • O(1): Describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set.
function firstItem(arr){ return arr[0];}

The above function firstItem(), will always take the same time to execute, as it returns the first item from an array, irrespective of its size. The running time of this function is independent of input size, and so it has a constant complexity of O(1).

Relating it to the above explanation, even in the worst case scenario of this algorithm (assuming input to be extremely large), the running time would remain constant and not go beyond a certain value. So, its BigO complexity is constant, that is O(1).

  • O(N): Describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set. Take a look at the example below. We have a function called matchValue() which returns true whenever a matching case is found in the array. Here, since we have to iterate over the whole of the array, the running time is directly proportional to the size of the array.
function matchValue(arr, k){ for(var i = 0; i < arr.length; i++){ if(arr[i]==k){ return true; } else{ return false; } } }

This also demonstrates how Big O favors the worst-case performance scenario. A matching case could be found during any iteration of the for loop and the function would return early. But Big O notation will always assume the upper limit (worst-case) where the algorithm will perform the maximum number of iterations.

  • O(N²): This represents an algorithm whose performance is directly proportional to the square of the size of the input data set. This is common with algorithms that involve nested iterations over the data set. Deeper nested iterations will result in O(N³), O(N⁴), etc.
function containsDuplicates(arr){ for (var outer = 0; outer < arr.length; outer++){ for (var inner = 0; inner < arr.length; inner++){ if (outer == inner) continue; if (arr[outer] == arr[inner]) return true; } } return false;}
  • O(2^N): Denotes an algorithm whose growth doubles with each addition to the input data set. The growth curve of an O(2^N) function is exponential — starting off very shallow, then rising meteorically. An example of an O(2^N) function is the recursive calculation of Fibonacci numbers:
function recursiveFibonacci(number){ if (number <= 1) return number; return recursiveFibonacci(number - 2) + recursiveFibonacci(number - 1);}

Are you getting the hang of this? Perfect. If not, feel free to fire up your queries in the comments below. :)

Moving on, now that we have a better understanding of the BigO notation, let us get to the next type of asymptotic analysis which is, the Big Omega(Ω).

The Big Omega (Ω)?

The Big Omega(Ω) provides us with the best case scenario of running an algorithm. Meaning, it would give us the minimum amount of resources (time or space) an algorithm would take to run.

Let’s dive into the mathematics of it to analyze it graphically.

We have an algorithm which can be described by a function f(n). So, to define the BigΩ of f(n), we need to find a function, let’s say, g(n), which is tightest to the lower bound of f(n). Meaning, after a certain value, n0, the value of f(n) would always exceed g(n).

We can write it as,

f(n)≥ C g(n)

where n≥n0; C> 0; n0≥1

If above conditions are fulfilled, we can say that g(n) is the BigΩ of f(n), or

f(n) = Ω (g(n))

Can we infer that Ω(…) is complementary to O(…)? Moving on to the last section of this post…

The Big Theta (θ)?

The Big Theta(θ) is a sort of a combination of both BigO and BigΩ. It gives us the average case scenario of running an algorithm. Meaning, it would give us the mean of the best and worst case. Let’s analyse it mathematically.

Considering an algorithm which can be described by a function f(n). The Bigθ of f(n) would be a function, let’s say, g(n), which bounds it the tightest by both lower and upper bound, such that,

C₁g(n) ≤ f(n)≤ C₂ g(n)

whereC₁, C₂ >0, n≥ n0,

n0 ≥ 1

Meaning, after a certain value, n0, the value of C₁g(n) would always be less than f(n), and value of C₂ g(n) would always exceed f(n).

Now that we have a better understanding of the different types of asymptotic complexities, let’s have an example to get a clearer idea of how all this works practically.

Consider an array, of size, say, n, and we want to do a linear search to find an element x in it. Suppose the array looks something like this in the memory.

Going by the concept of linear search, if x=9, then that would be the best case scenario for the following case (as we don’t have to iterate over the whole array). And from what we have just learned, the complexity for this can be written as Ω(1). Makes sense?

Similarly, if x were equal to 14, that would be the worst case scenario, and the complexity would have been O(n).

What would be the average case complexity for this?

θ(n/2) => 1/2 θ(n) => θ(n) (As we ignore constants while calculating asymptotic complexities).

So, there you go folks. A fundamental insight into algorithmic complexities. Did it go well with you? Leave your advice, questions, suggestions in the comments below. Thanks for reading!❤️

References:-

  • A nice write-up by Dionysis “dionyziz” Zindros: //discrete.gr/complexity/
  • A good series on algorithm & data structures: //interactivepython.org/runestone/static/pythonds/AlgorithmAnalysis/WhatIsAlgorithmAnalysis.html