Kompleksitas waktu dalam melintasi array

Di bawah ini adalah dua cara saya dapat melintasi array apa pun:

  1. Menggunakan loop for, suatu variabel akan melintasi dari awal hingga akhir array.
  2. Menggunakan variabel while loop 2 akan melintasi dari arah yang berlawanan dan bertemu di antara keduanya.

Bagaimana kompleksitas waktunya bervariasi, apakah akan berkurang pada kasus kedua atau akan sama?


traversal time-complexity
person Adarsh Mohanty    schedule 23.08.2020    source sumber
comment
Hal yang sama terjadi pada kedua kasus karena Anda masih mengunjungi setiap elemen array hanya sekali.   -  person Dai    schedule 23.08.2020
comment
@Dai Bukankah kompleksitas waktu menjadi lebih kecil dengan faktor 2? Kompleksitas ruang akan sama tetapi secara teoritis metode ke-2 harus mengambil O(n/2) (tentu saja tidak memperhitungkan pembulatan ke O(n))   -  person Alex.Kh    schedule 23.08.2020
comment
Coba pikirkan seperti ini -› sebenarnya bukan pengambilan elemen yang memerlukan biaya apa pun, namun apa pun yang Anda lakukan dengan elemen arraylah yang memerlukan biaya. Biaya tersebut tetap harus dibayar satu kali untuk setiap elemen, meskipun Anda mengeluarkan dua elemen lalu mengoperasikannya secara terpisah.   -  person g.d.d.c    schedule 23.08.2020
comment
@Alex.Kh Notasi Big-O (dan kompleksitas waktu secara umum) hanya berkaitan dengan urutan fungsi (laju pertumbuhan), jadi jika Anda memiliki algoritma O(1) yang selalu membutuhkan waktu tepat 1.000.000 tahun pada CPU saat ini dan algoritma lain untuk masalah yang sama yang berjalan dalam waktu O(n^2) (tetapi berjalan hanya dalam beberapa milidetik karena beberapa optimasi CPU yang membuat setiap operasi menjadi sangat murah, tetapi masih perlu dijalankan n^2 kali) maka itu tidak mengubah kompleksitas waktu dan jutaan Algoritma -year masih tidak terlalu rumit dalam hal waktu.   -  person Dai    schedule 23.08.2020

Jawaban (1)


arrow_upward
0
arrow_downward

Tentu saja sama. Keduanya adalah O(n), pada kenyataannya tidak ada cara untuk melintasi array lebih cepat dari O(n). Bahkan jika Anda melakukan tarverse dari arah yang berlawanan, Anda masih harus mengunjungi setiap elemen satu kali.

person haoyu wang    schedule 23.08.2020
comment
itu karena Anda tidak melakukan banyak hal dalam perulangan Anda, sehingga waktu perulangan menjadi bagian yang paling memakan waktu. Namun di dunia nyata, Anda biasanya harus melakukan beberapa pemrosesan untuk setiap elemen, dalam hal ini perulangan while tidak akan menghemat banyak waktu. - person haoyu wang; 23.08.2020
comment
sebenarnya tidak ada cara untuk melintasi array lebih cepat dari O(n) - Saya akan menjadi orang yang pintar di sini: jika kita berbicara tentang array (atau vektor atau tupel) < b>khususnya maka jika panjangnya n dibatasi menjadi n <= hardware-units maka ada algoritma O(1) (misalnya SIMD dan implementasinya di SSE). Saya berpendapat bahwa ini adalah algoritma O(1) yang benar karena tingkat pertumbuhan dari algoritma tersebut adalah nol dan ketika n terlalu besar maka algoritma tersebut benar-benar tidak dapat bekerja. Katakan saja (dalam praktiknya SIMD seperti yang digunakan dalam algoritme akhirnya mendukung n sewenang-wenang sehingga O(n)) - person Dai; 23.08.2020