زمان اجرای الگوریتم جستجوی دودویی

[kluivert]

سلام
می خواستم ببینم پیچیدگی زمان اجرای الگوریتم دودویی وقتی روی آرایه انجام میشه با وقتی که روی لیست پیوندی انجام میشه یکی است؟ مرسی

[Exception]

سلام
می خواستم ببینم پیچیدگی زمان اجرای الگوریتم دودویی وقتی روی آرایه انجام میشه با وقتی که روی لیست پیوندی انجام میشه یکی است؟ مرسی
الگوریتم مستقل از ساختمان داده است! اما مشکل اینجاست که در جستجوی دودویی، ساختمان داده ای با دسترسی تصادفی نیاز داری و لیست پیوندی این خاصیت رو نداره.
بنابراین اصلا نمیتونی این الگوریتم رو روی لیست پیوندی اجرا کنی و مجبوری یه جورایی دسترسی تصادفی رو شبیه سازی کنی که این خودش باعث میشه پیچیدگی زمانی زیاد بشه!
شرمنده یکمی گیج کننده شد، ولی باز هم منظور رو میرسونه!

[mortezamsp]

فکرکنم در جست و جوی دودویی در لیست پیوندی (!) باید برای پیداکردن هرگره یک بار لیست رو پیمایش کنی که دراینصورت باید پیچیدگی در n ضرب بشه و میشه : o( n log n )