Menemukan simpul dalam kompleksitas waktu daftar tertaut tunggal

Saya memiliki pertanyaan ini dalam ujian tengah semester Kursus DSA saya:

Misalkan Single Linked List berisi N node (N > 8), metode f1() dirancang untuk mencari node ke-8 dari awal, dan metode f2() dirancang untuk menemukan node ke-8 dari akhir. Berapakah kompleksitas waktu dari f1() dan f2()?

Pilih satu:

A. Terus menerus)

B. HAI(1) dan HAI(1)

C. HAI(1) dan HAI(N)

D. PADA(N) dan O(1)

Jawaban yang benar yang diberikan adalah c. HAI(1) dan HAI(N). Namun menurut saya jawaban yang benar adalah a. Saya tahu jika N = 8 akan memerlukan waktu O(1) untuk menemukan simpul ke-8 dari awal (kembalikan saja simpul ekornya) tetapi dalam kasus ini N > 8. Adakah yang bisa menjelaskan ini untuk saya?

Terima kasih sebelumnya atas bantuan apa pun yang dapat Anda berikan.


list algorithm data-structures linked-list singly-linked-list
person L.I.B L.I.B    schedule 18.05.2016    source sumber
comment
Jawaban yang diberikan benar, Anda salah. Berapa banyak operasi yang Anda perlukan untuk mengembalikan node ke-8 dari 1000? Dari 1000.000?   -  person n. 1.8e9-where's-my-share m.    schedule 18.05.2016
comment
C. adalah yang paling benar, tetapi a. secara teknis juga benar, karena apa pun yang O(1) juga O(N).   -  person Paul Hankin    schedule 19.05.2016

Jawaban (1)


arrow_upward
1
arrow_downward

O(1) menyiratkan waktu berjalan yang konstan. Dengan kata lain, ini tidak bergantung pada ukuran input.

Saat Anda menerapkan definisi tersebut di sini, Anda dapat melihat bahwa pengambilan elemen ke-8 selalu merupakan operasi konstan terlepas dari ukuran inputnya. Hal ini karena, berapa pun ukuran inputnya (misal: 10,100,100..), operasi get(8) akan selalu memakan waktu yang sama. Selain itu, karena kita mengetahui dengan pasti bahwa n > 8, tidak ada kemungkinan mencoba mengambil elemen ke-8 akan menghasilkan ukuran input yang melebihi ukuran input.

person attaboy182    schedule 18.05.2016
comment
O(1) tidak berarti waktu berjalan yang konstan, juga tidak bergantung pada ukuran masukan. Sebaliknya, ini menyiratkan bahwa waktu berjalan dibatasi oleh sebuah konstanta. - person Paul Hankin; 19.05.2016
comment
@PaulHankin intinya adalah mencoba membuat seseorang mengerti O(1) . Ada alasan mengapa saya menggunakan kata menyiratkan. - person attaboy182; 19.05.2016
comment
Tentu, tetapi ada banyak kesalahpahaman tentang O besar dan kompleksitas dan menurut saya jawaban yang baik tidak perlu menyertakan kesalahan. Mungkin: O(1) berarti bahwa program tidak akan memakan waktu lebih dari jumlah waktu yang tetap, apa pun masukannya. - person Paul Hankin; 19.05.2016