Notasi besar dalam struktur data: Semua yang perlu diketahui

Notasi Big O dalam struktur data digunakan untuk menentukan efisiensi suatu algoritma, jumlah waktu yang dibutuhkan untuk menjalankan fungsi dengan pertumbuhan input, dan seberapa baik skala fungsi. Pengukuran efisiensi ini dapat dibagi menjadi dua bagian, yaitu kompleksitas ruang dan kompleksitas waktu.

Notasi Big O mengacu pada notasi matematika yang bertindak sebagai faktor pembatas dari fungsi apa pun ketika sebuah argumen lebih cenderung condong ke nilai atau tak terhingga tertentu. Itu termasuk dalam kategori notasi matematika yang ditemukan oleh Edmund Landau, Paul Bachmann, dan lainnya. Oleh karena itu, secara kolektif disebut notasi Bachmann-Landau atau notasi asimtotik.

Sesuai deduksi matematika, dua fungsi, f(n) dan g(n) didefinisikan pada himpunan bilangan positif atau real yang tidak terikat. Di sini, g(n) benar-benar positif untuk setiap nilai besar n. Itu dapat ditulis dengan cara berikut:

f(n) = O(g(n)) di mana n cenderung tak terhingga (n → )

Namun, di sini, pengandaian n hingga tak terhingga tidak didefinisikan secara eksklusif, dan oleh karena itu ekspresi di atas dapat ditulis sebagai:

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

Di sini, f dan g adalah fungsi penting yang dimulai dari bilangan bulat positif hingga bilangan real yang bukan non-negatif.

Oleh karena itu, nilai n besar dilambangkan dengan asimtotik O Besar.

Sifat Notasi O Besar dalam Struktur Data

Algoritma Big O dalam struktur data memiliki beberapa properti wajib yang diperlukan. Sifat-sifat penting Notasi O Besar tersebut adalah sebagai berikut:

• Fungsi Penjumlahan:
  Jika f(n) = f 1 (n) + f 2 (n) + — + f m (n) dan f i (n)≤ f i +1(n) ∀ i=1, 2,–, m,
  maka O(f(n)) = O(maks(f1(n), f2(n), –, fm(n))).
• Fungsi Logaritma:
  Jika f(n) = logan dan g(n)=logbn,
  maka O(f(n))=O(g(n))
• Perkalian Konstan:
  Jika f(n) = cg(n), maka O(f(n)) = O(g(n)) di mana c adalah konstanta bukan nol.
• Fungsi Polinomial:
  Jika f(n) = a0 + a1.n + a2.n2 + — + am.nm,
  maka O(f(n)) = O(nm).

Pelajari Kursus Pengembangan Perangkat Lunak online dari Universitas top dunia. Dapatkan Program PG Eksekutif, Program Sertifikat Tingkat Lanjut, atau Program Magister untuk mempercepat karier Anda.

Jelajahi Kursus Rekayasa Perangkat Lunak Populer kami

Di sini, saat menangani Big O, setiap fungsi log meningkat dengan cara yang sama.

Pentingnya Notasi O Besar Dalam Analisis Runtime Algoritma

Kompleksitas waktu berjalan kasus terburuk dari algoritma digunakan untuk menarik perbandingan dan menghitung, terutama dalam hal menganalisis kinerja suatu algoritma. Urutan O(1), digambarkan sebagai Waktu Berjalan Konstan, adalah waktu berjalan tercepat algoritme – waktu yang dibutuhkan algoritme sama untuk berbagai ukuran input. Penting untuk dicatat bahwa runtime ideal dari suatu algoritma adalah waktu berjalan yang konstan, yang sangat jarang dicapai karena runtime algoritma bergantung pada ukuran input n.

Sebagai contoh:

Seperti disebutkan di atas, kinerja runtime algoritme sangat bergantung pada ukuran input n. Mari kita jelaskan fakta ini dengan beberapa contoh matematika untuk membuat analisis runtime dari suatu algoritma untuk berbagai ukuran n:

• n = 20
  log (20) = 2,996;
  20 = 20;
  20 log (20) = 59,9;
  20 2 = 400;
  2 20 = 1084576;
  20! = 2.432902 + 18 18 ;
• n = 10
  log (10) = 1;
  10 = 10;
  10 log (10) = 10;
  10 2 = 100;
  2 10 = 1024;
  10! = 3628800;

Kinerja runtime dari suatu algoritma dihitung dengan cara yang sama.

Berikut adalah beberapa contoh algoritmik lain dari analisis runtime –

• Ketika datang ke Pencarian Linear, kompleksitas runtime adalah O(n).
• Kompleksitas runtime adalah O(log n) untuk pencarian biner.
• Untuk Selection Sort, Bubble Sort, Bucket Sort, Insertion Sort, kompleksitas runtime adalah O(n^c).
• Ketika datang ke algoritma Eksponensial seperti Tower of Hanoi, kompleksitas runtime adalah O(c^n).
• Untuk Merge SortSort dan Heap Sort, kompleksitas runtime adalah O(n log n).

Bagaimana Big O menganalisis kompleksitas ruang?

Menentukan kompleksitas ruang dan runtime untuk suatu algoritma adalah langkah penting. Ini karena kita dapat menentukan waktu eksekusi yang dibutuhkan suatu algoritme dengan menganalisis kinerja runtime algoritme dan ruang memori yang diambil algoritme melalui analisis kompleksitas ruang algoritme. Oleh karena itu, untuk mengukur kompleksitas ruang suatu algoritma, kita harus membandingkan kinerja kompleksitas ruang kasus terburuk dari algoritma tersebut.

Untuk menentukan kompleksitas ruang suatu algoritma, kita harus mengikuti dua tugas ini –

Tugas 1: Sangat penting untuk mengimplementasikan program untuk algoritma tertentu.

Tugas 2: Penting untuk mengetahui ukuran input n untuk menentukan memori yang akan ditampung setiap item.

Kedua tugas penting ini harus diselesaikan sebelum menghitung kompleksitas ruang untuk suatu algoritma.

Contoh Algoritma Kompleksitas Ruang

Ada banyak contoh algoritme dengan kompleksitas ruang, beberapa di antaranya telah disebutkan di bawah ini untuk pemahaman yang lebih baik tentang jenis algoritme ini:

• Untuk Bubble sort, Linear Search, Selection sort, Insertion sort, Heap sort, dan Binary Search, kompleksitas ruangnya adalah O(1) .
• Kompleksitas ruang adalah O(n+k) dalam hal radix sort .
• Kompleksitas ruang adalah O(n) untuk SortSort cepat.
• Kompleksitas ruang adalah O(log n) untuk sortir gabungan.

Contoh Notasi O Besar dalam C

Adalah fakta bahwa notasi Big O terutama digunakan dalam Ilmu Komputer untuk menentukan kompleksitas atau kinerja suatu algoritma. Notasi ini memberi kita kemampuan untuk mengklasifikasikan perilaku algoritme berdasarkan pertumbuhan ruang memori atau persyaratan waktu eksekusi ketika jumlah data input menjadi besar. Ini tidak dirancang untuk memprediksi penggunaan memori aktual atau waktu eksekusi tetapi untuk membandingkan algoritma dan kemudian memilih yang terbaik di antara mereka untuk pekerjaan itu. Ini tidak spesifik bahasa tetapi juga diimplementasikan dalam C.

Di bawah ini, Anda akan menemukan algoritme pengurutan pemilihan di C di mana kompleksitas kasus terburuk (notasi O Besar) dari algoritme telah dihitung:-

untuk(int i=0; i<n; i++)

{

int min = saya;

untuk(int j=i; j<n; j++)

{

if(array[j]<array[min])

min=j;

}

int suhu = array[i];

array[i] = array[min];

array[mnt] = suhu;

}

Untuk menganalisis algoritma:

• Sudah dapat dilambangkan bahwa range dari for outer loop adalah i < n , yang menyatakan bahwa orde loop adalah O(n).
• Selanjutnya, kita dapat mengidentifikasi bahwa itu juga O(n) sebagai j < n untuk loop for dalam.
• Konstanta diabaikan, bahkan jika efisiensi rata-rata ditemukan n/2 untuk konstanta c. Jadi, ordenya adalah O(n).
• Setelah mengalikan urutan loop dalam dan loop luar, kompleksitas runtime yang dicapai adalah O(n^2).

Algoritma lain dalam C dapat dengan mudah diimplementasikan, di mana kompleksitasnya dapat dengan mudah dianalisis dan ditentukan dengan cara yang sama.

Penggunaan Notasi O Besar

Ada dua area utama di mana Notasi O Besar diterapkan: -

• Matematika : Notasi O Besar cukup umum digunakan dalam bidang matematika untuk menggambarkan bagaimana deret hingga mendekati suatu fungsi, terutama dalam kasus ekspansi asimtotik atau deret Taylor terpotong.
• Ilmu komputer: Ini adalah fakta mapan bahwa notasi Big O banyak digunakan di bidang ilmu komputer karena kegunaannya dalam analisis algoritma

Namun, dalam kedua aplikasi, fungsi g ( x ) yang muncul di dalam O (·) sering kali dipilih sebagai yang paling sederhana jika suku orde rendah dan faktor konstan dihilangkan.

Ada dua penggunaan lain dari notasi ini yang secara formal dekat tetapi relatif berbeda. Mereka:-

• Asimtotik tak terbatas
• asimtotik tak terhingga.

Namun, perbedaan ini tidak pada prinsipnya, dalam penerapannya hanya dengan definisi formal untuk "O Besar" yang sama persis untuk kedua kasus. Satu-satunya perbedaan adalah batas argumen fungsi.

Baca Artikel Populer kami yang terkait dengan Pengembangan Perangkat Lunak

Kesimpulan

Sebagai kesimpulan, kita dapat mengatakan bahwa Big Data memainkan peran integral dalam struktur data, dan memiliki pengetahuan yang mendalam dan komprehensif tentang notasi Big O adalah keterampilan yang sangat baik untuk dimiliki. Ini sangat diminati di sektor pekerjaan dan berpotensi menjadi pilihan tepat untuk jalur karier. Program Sertifikat Tingkat Lanjut upGrad dalam Big Data akan memberi Anda pengaruh yang Anda butuhkan untuk meningkatkan karier Anda. Ini akan memperkenalkan Anda pada keterampilan profesional terbaik seperti Pemrosesan Data dengan PySpark, Data Warehousing, MapReduce, Pemrosesan Data Besar di AWS Cloud, Pemrosesan Waktu Nyata, dll.