java algorithms collections

Algoritma dan Koleksi Java

Koleksi Data Kustom untuk Wawancara Teknis untuk Peran Pengembang Java Junior.

Algoritma

Lihat seluruh daftar di sini

Notasi o besar

• Kompleksitas Waktu : Estimasi jumlah operasi atau langkah yang perlu dijalankan algoritma sebagai fungsi dari ukuran input.
• Kompleksitas ruang : Jumlah maksimum memori tambahan yang diperlukan suatu algoritma untuk mengalokasikan atau digunakan selama pelaksanaannya sebagai fungsi dari ukuran input.
  • Ruang bantu adalah ruang ekstra atau ruang sementara yang digunakan oleh suatu algoritma.

n dalam kompleksitas waktu - jumlah elemen dalam input.

n Dalam kompleksitas ruang - ukuran input dalam satuan bit yang diperlukan untuk mewakili input.

Tabel kompleksitas waktu besar

Jenis	Nama	Penjelasan	Status	Contoh
O(1)	Waktu konstan	Algoritma dieksekusi jumlah yang sama setiap kali, terlepas dari ukuran input	Bagus sekali	Cari di tabel hash dengan kunci
O(log n)	Waktu logaritma	Waktu eksekusi meningkat sangat lambat dibandingkan dengan peningkatan ukuran data input	Bagus sekali	Pencarian biner (rata -rata)
O(n)	Waktu linier	Waktu eksekusi sebanding secara linear dengan ukuran data input	Bagus	Pencarian brute force
O(n + k)	Waktu gabungan/aditif	Kombinasi kompleksitas dua input terpisah	Bagus	Menghitung jenis
O(n log n)	Waktu quasilinear	Dengan meningkatnya ukuran input, jumlah divisi yang diperlukan untuk menyelesaikan masalah meningkat secara perlahan karena pertumbuhan logaritmik	Buruk	Gabungan, jenis heap
O(n^2)	Waktu kuadratik	Melibatkan iterasi atau perbandingan bersarang untuk setiap elemen	Mengerikan	Jenis seleksi
O(2^n)	Waktu eksponensial	Melibatkan pencarian atau penghitungan yang lengkap dari semua kemungkinan kombinasi input, waktu eksekusi meningkat secara eksponensial	Mengerikan	TSP (pemrograman dinamis)
O(n!)	Waktu faktorial	Melibatkan pencarian atau penghitungan yang lengkap dari semua kemungkinan kombinasi input, waktu eksekusi meningkat secara faktor	Mengerikan	TSP (brute force)

Tabel kompleksitas ruang big-o

Jenis	Nama	Penjelasan	Status	Contoh
O(1)	Ruang konstan	Algoritma membutuhkan jumlah memori tambahan yang tetap, terlepas dari ukuran input	Bagus sekali	Sortir tumpukan
O(log n)	Ruang Logaritmik	Penggunaan ruang meningkat secara perlahan dibandingkan dengan peningkatan ukuran data input	Bagus sekali	Sortir cepat
O(n)	Ruang linier	Skala penggunaan ruang secara linear dengan ukuran input	Bagus	Gabungan
O(n + k)	Ruang gabungan/aditif	Skala penggunaan ruang secara linear dengan jumlah n dan k	Buruk	Radix Sort

Definisi

Ketentuan	Definisi	Contoh
Abstrak Tipe Data (ADT)	Mewakili deskripsi tingkat tinggi dari tipe data, dengan fokus pada perilaku dan operasinya daripada detail implementasi spesifik	tumpukan, antrian, kamus, urutan, set
Struktur data	Teknik atau strategi untuk mengimplementasikan tipe data tertentu, mengatur dan menyimpan data dengan cara tertentu untuk memfasilitasi operasi yang efisien	Array, daftar tertaut, tabel hash, pohon (pohon pencarian biner, tumpukan, pohon merah/hitam

Kelas Koleksi Java

• Koleksi
  • Mengatur
    • Hashset
    • LinkedHashset
      • Sortedset
      • Navigableset
        • Treeset
  • Daftar
    • Daftar Array
    • LinkedList
    • Vektor
      • Tumpukan
  • Antre
    • Antrian prioritas
      • Deque
        • Arraydequeue
• Peta
  • Hashtable
  • Hashmap
  • LinkedHashMap
    • Sortedmap
    • Navigablemap
      • TreeMap

Membandingkan jenis koleksi:

Jenis	Elemen duplikat	Urutan elemen	Harus menambahkan/menghapus dalam urutan tertentu
Daftar	Diizinkan	Dengan indeks	TIDAK
Peta	Diizinkan untuk nilai	Java menggunakan hashcode () dari kunci untuk menentukan urutan, bagi kami itu tidak diurutkan	TIDAK
Antre	Diizinkan	Diperoleh dalam urutan yang ditentukan	Ya
Mengatur	Dilarang	Hanya di Treeset	Ya

Atribut Koleksi:

Jenis	Antarmuka	Disortir?	Panggilan hashCode() ?	Panggilan compareTo() ?
Daftar Array	Daftar	TIDAK	TIDAK	TIDAK
LinkedList	Daftar, Deque	TIDAK	TIDAK	TIDAK
Arraydeque	Antrian, Deque	TIDAK	TIDAK	TIDAK
Hashset	Mengatur	TIDAK	Ya	TIDAK
Treeset	Set, sortedset	Ya	TIDAK	Ya
LinkedHashset	Mengatur	TIDAK	Ya	TIDAK
Hashmap	Peta	TIDAK	Ya	TIDAK
LinkedHashMap	Peta	TIDAK	Ya	TIDAK
TreeMap	Peta, sortedmap	Ya	TIDAK	Ya

Struktur data yang melibatkan penyortiran tidak mengizinkan nilai nol.