Apa beberapa algoritma yang kita gunakan setiap hari yang memiliki kompleksitas O (1), O (n log n) dan O (log n)?

Jika Anda menginginkan contoh Algoritma / Kelompok Pernyataan dengan kompleksitas Waktu seperti yang diberikan dalam pertanyaan, berikut adalah daftar kecilnya -

O(1) waktu

• Mengakses Indeks Array (int a = ARR [5];)
• Memasukkan node dalam Daftar Tertaut
• Mendorong dan Meletuskan Stack
• Penyisipan dan Penghapusan dari Antrian
• Mencari tahu orang tua atau anak kiri / kanan dari sebuah node di pohon yang disimpan di Array
• Melompat ke elemen Berikutnya / Sebelumnya dalam Daftar Tertaut Ganda

O(n) waktu

Singkatnya, semua Algoritma Brute Force, atau Noob yang membutuhkan linearitas, didasarkan pada kompleksitas waktu O (n)

• Melintasi array
• Melintasi daftar tertaut
• Pencarian Linier
• Penghapusan elemen tertentu dalam Daftar Tertaut (Tidak diurutkan)
• Membandingkan dua string
• Memeriksa Palindrome
• Menghitung / Menyortir Ember dan di sini juga Anda dapat menemukan jutaan contoh lainnya ....

O(log n) waktu

• Pencarian Biner
• Menemukan bilangan terbesar / terkecil dalam pohon pencarian biner
• Algoritma Divide and Conquer tertentu berdasarkan fungsionalitas Linear
• Menghitung Bilangan Fibonacci - Metode Terbaik Premis dasar di sini BUKAN menggunakan data lengkap, dan mengurangi ukuran masalah dengan setiap iterasi

O(n log n) waktu

Faktor 'log n' diperkenalkan dengan mempertimbangkan Divide and Conquer. Beberapa dari algoritma ini adalah yang paling optimal dan sering digunakan.

• Gabungkan Sortir
• Urutan Heap
• Sortir Cepat
• Algoritma Divide and Conquer tertentu berdasarkan pada algoritma O (n ^ 2) yang dioptimalkan

O(n^2) waktu

Algoritma ini seharusnya menjadi algoritma yang kurang efisien jika pasangan O (nlogn) mereka ada. Penerapan umum mungkin Brute Force di sini.

• Bubble Sort
• Sortir Penyisipan
• Sortir Pilihan
• Melintasi array 2D sederhana

Contoh sederhana dari O(1)mungkin return 23;- apa pun masukannya, ini akan kembali dalam waktu yang tetap dan terbatas.

Contoh tipikal O(N log N)akan menyortir array input dengan algoritma yang baik (misalnya mergesort).

Contoh tipikal jika O(log N)akan mencari nilai dalam larik input yang diurutkan menurut pembagian.

O (1) - sebagian besar prosedur memasak adalah O (1), artinya, dibutuhkan jumlah waktu yang konstan bahkan jika ada lebih banyak orang untuk memasak (sampai tingkat tertentu, karena Anda dapat kehabisan ruang di panci / wajan Anda dan perlu membagi masakan)

O (logn) - menemukan sesuatu di buku telepon Anda. Pikirkan pencarian biner.

O (n) - membaca buku, di mana n adalah jumlah halaman. Ini adalah jumlah waktu minimum yang diperlukan untuk membaca buku.

O (nlogn) - tidak dapat langsung memikirkan sesuatu yang mungkin dilakukan setiap hari yaitu nlogn ... kecuali jika Anda mengurutkan kartu dengan melakukan merge atau quick sort!

Saya dapat menawarkan beberapa algoritma umum ...

• O (1): Mengakses elemen dalam array (yaitu int i = a [9])
• O (n log n): quick atau mergesort (Rata-rata)
• O (log n): Pencarian biner

Ini akan menjadi tanggapan yang tepat karena ini terdengar seperti pertanyaan pekerjaan rumah / wawancara. Jika Anda mencari sesuatu yang lebih konkret, itu sedikit lebih sulit karena publik pada umumnya tidak akan tahu tentang implementasi yang mendasari (tentu saja menghemat sumber terbuka) dari aplikasi populer, juga tidak konsep secara umum berlaku untuk "aplikasi"

O (1): menemukan langkah terbaik berikutnya dalam Catur (atau Pergi dalam hal ini). Karena jumlah status game terbatas, hanya O (1) :-)

Kompleksitas aplikasi perangkat lunak tidak diukur dan tidak ditulis dalam notasi big-O. Mengukur kompleksitas algoritma dan membandingkan algoritma dalam domain yang sama hanya berguna. Kemungkinan besar, ketika kita mengatakan O (n), yang kita maksud adalah "O (n) perbandingan " atau "O (n) operasi aritmatika". Artinya, Anda tidak dapat membandingkan pasangan algoritme atau aplikasi apa pun.

O (1) - Menghapus elemen dari daftar tertaut ganda. misalnya

typedef struct _node {
    struct _node *next;
    struct _node *prev;
    int data;
} node;


void delete(node **head, node *to_delete)
{
    .
    .
    .
}

Anda dapat menambahkan algoritme berikut ke daftar Anda:

O(1)- Menentukan apakah suatu bilangan genap atau ganjil; Bekerja dengan HashMap

O(logN) - menghitung x ^ N,

O(N Log N) - Peningkatan urutan terlama

O (n log n) terkenal sebagai batas atas seberapa cepat Anda dapat mengurutkan himpunan arbitrer (dengan asumsi model komputasi standar dan tidak terlalu paralel).

0 (logn) -Pencarian biner, elemen puncak dalam sebuah array (bisa ada lebih dari satu puncak) 0 (1) -in python menghitung panjang daftar atau string. Fungsi len () membutuhkan 0 (1) waktu. Mengakses elemen dalam larik membutuhkan 0 (1) waktu. Operasi dorong dalam tumpukan membutuhkan waktu 0 (1) kali. 0 (nlogn) -Gabungkan semacam. menyortir dengan python membutuhkan waktu nlogn. jadi ketika Anda menggunakan listname.sort () dibutuhkan waktu nlogn.

Catatan-Pencarian dalam tabel hash terkadang membutuhkan lebih dari waktu konstan karena benturan.

O (2 ^N )

O (2 ^N ) menunjukkan algoritma yang pertumbuhannya berlipat ganda dengan setiap penambahan ke kumpulan data masukan. Kurva pertumbuhan suatu fungsi O (2 ^N ) bersifat eksponensial - dimulai dari sangat dangkal, kemudian naik secara meteorik. Contoh dari fungsi O (2 ^N ) adalah perhitungan rekursif dari bilangan Fibonacci:

int Fibonacci (int number)
{
if (number <= 1) return number;
return Fibonacci(number - 2) + Fibonacci(number - 1);
}