- شروع کننده موضوع
- #1
armita
کاربر خاک‌انجمن‌خورده
- ارسال‌ها
- 2,204
- امتیاز
- 686
- نام مرکز سمپاد
- دبیرستان فرزانگان ۱
- شهر
- تهران
- دانشگاه
- شریف
- رشته دانشگاه
- علوم کامپیوتر
جستجوی خطی
جستجوی خطی (linear search) یا جستجوی ترتیبی (sequential search) کلیه عناصر درون یک لیست را یکی یکی بررسی می کند تا آرگومان جستجو پیدا شود.
اگر تعداد عناصر مجموعه n باشد، زمان جستجو O(n) است. بهترین حالت زمانی اتفاق می افتد که آرگومان جستجو برابر با اولین عنصر لیست باشد که با یک مقایسه پیدا می شود. بدترین حالت وقتی است که داده درون لیست وجود ندارد یا در انتهای لیست واقع شده است که n مقایسه مورد نیاز است.
اگر تعداد عناصر کم باشد جستجوی خطی به دلیل سادگی از الگوریتم های پیچیده دیگر مناسب تر است. برای لیست های نامرتب اغلب جستجوی خطی اولین انتخاب است. کارائی الگوریتم روی یک لیست مرتب بالا می رود. در این حالت به جای رسیدن به انتهای لیست، جستجو با رسیدن به اولین عنصری که بزرگتر(یا کوچکتر) از آرگومان جستجو است خاتمه پیدا می کند.
جستجوی دودوئی
الگوریتم جستجوی دودوئی (binary search algorithm) روشی برای جستجوی یک مقدار درون یک لیست مرتب است. عنصر وسط لیست انتخاب شده و با آرگومان جستجو مقایسه می شود تا تعیین شود از آن بزگتر، کوچکتر یا مساوی است. اگر آرگومان از عنصر انتخاب شده بزرگتر باشد جستجو در نیمه پایینی و اگر کوچکتر باشد در نیمه بالائی لیست ادامه پیدا می کند.
زمان جستجو O(log n) است که زمان بهتری نسبت به جستجوی خطی است. اگر آرگومان جستجو برابر با عنصر وسط لیست باشد با یک مقایسه پیدا می شود که بهترين حالت است. در بدترین حالت به ⌊log2 n ⌋ + 1 مقايسه نياز است.
فکر کنم الگوریتم های دیگه ای هم برای جستجو در یک آرایه مرتب وجود داشته باشن ، ولی من هر چی گشتم چیزی پیدا نکردم !
اگر اطلاعی دارین خوش حال میشم به ما هم بگین
!
جستجوی خطی (linear search) یا جستجوی ترتیبی (sequential search) کلیه عناصر درون یک لیست را یکی یکی بررسی می کند تا آرگومان جستجو پیدا شود.
اگر تعداد عناصر مجموعه n باشد، زمان جستجو O(n) است. بهترین حالت زمانی اتفاق می افتد که آرگومان جستجو برابر با اولین عنصر لیست باشد که با یک مقایسه پیدا می شود. بدترین حالت وقتی است که داده درون لیست وجود ندارد یا در انتهای لیست واقع شده است که n مقایسه مورد نیاز است.
اگر تعداد عناصر کم باشد جستجوی خطی به دلیل سادگی از الگوریتم های پیچیده دیگر مناسب تر است. برای لیست های نامرتب اغلب جستجوی خطی اولین انتخاب است. کارائی الگوریتم روی یک لیست مرتب بالا می رود. در این حالت به جای رسیدن به انتهای لیست، جستجو با رسیدن به اولین عنصری که بزرگتر(یا کوچکتر) از آرگومان جستجو است خاتمه پیدا می کند.
جستجوی دودوئی
الگوریتم جستجوی دودوئی (binary search algorithm) روشی برای جستجوی یک مقدار درون یک لیست مرتب است. عنصر وسط لیست انتخاب شده و با آرگومان جستجو مقایسه می شود تا تعیین شود از آن بزگتر، کوچکتر یا مساوی است. اگر آرگومان از عنصر انتخاب شده بزرگتر باشد جستجو در نیمه پایینی و اگر کوچکتر باشد در نیمه بالائی لیست ادامه پیدا می کند.
زمان جستجو O(log n) است که زمان بهتری نسبت به جستجوی خطی است. اگر آرگومان جستجو برابر با عنصر وسط لیست باشد با یک مقایسه پیدا می شود که بهترين حالت است. در بدترین حالت به ⌊log2 n ⌋ + 1 مقايسه نياز است.
فکر کنم الگوریتم های دیگه ای هم برای جستجو در یک آرایه مرتب وجود داشته باشن ، ولی من هر چی گشتم چیزی پیدا نکردم !
اگر اطلاعی دارین خوش حال میشم به ما هم بگین
!