‎$n$‎ عنصر در یک مجموعه وجود دارد. هر عنصر یک کلید یکتا و مقداری اطلاعات دارد. دنباله‌ای از درخواست‌ها به طول ‎$m$‎ به ما داده می‌شود، به‌طوری‌که هر درخواست با ارائه‌ی کلید، اطلاعات مربوطه را می‌خواهد. برای پاسخگویی به این درخواست‌ها از داده‌ساختاری به صورت یک لیست پیوندی بهره می‌بریم. الگوریتم ما برای راه‌اندازی هر درخواست، از ابتدای لیست کار را شروع می‌کند و با پیمایش آن به عنصر مطلوب می‌رسد و سپس بسته‌ی اطلاعاتی مربوط به آن را بازمی‌گرداند. اگر عنصر درخواستی در ‎$i$‎اُمین جایگاه لیست قرار داشته باشد، این عملیات ‎$i$‎ واحد هزینه خواهد داشت. پیش از بازگشت از رویه‌ي جستجو می‌توان بدون متحمل شدن هزینه‌ی اضافی، عنصر یافت شده را، هر مقدار که بخواهیم، به سر لیست نزدیک‌تر کنیم. از سوی دیگر، هرگاه که اراده کنیم، می‌توان جای دو عنصر متوالی لیست را با یک واحد هزینه جابجا کرد.

الگوریتم ‎«الف»‎ به این شکل عمل می‌کند که پس از یافتن هر عنصر، آن را یک واحد به سر لیست نزدیک می‌کند، به این امید که در ادامه کارایی جستجو را افزایش دهد.

الگوریتم‌ها به دو دسته‌ی ‎«برخط»‎ و ‎«برون‌خط»‎ تقسیم می‌شوند. دسته‌ی اوّل الگوریتم‌هایی هستند که درخواست‌ها را یکی‌یکی دریافت کرده و باید پیش از اطلاع از درخواست بعدی پاسخ را تحویل دهند. اما الگوریتم‌های ‎«برون‌خط»‎ در ابتدا همه‌ی درخواست‌ها را در اختیار دارند و می‌توانند حین اجرا از نحوه‌ی درخواست‌های بعدی نیز برای تصمیم در مورد تغییر ساختار لیست سود جویند.

الگوریتم ‎«ب»‎ بهترین الگوریتم ‎«برون‌خط»‎ است، بدین مفهوم که با داشتن دنباله درخواست‌ها در ابتدا، ساختار لیست را طوری حین عملیات تغییر می‌دهد که در نهایت کم‌ترین هزینه پیش آید.

الگوریتم برخطِ ‎«پ»‎ را $c$-‎رقابتی می‌نامیم، هرگاه ثابت ‎$a$‎ یافت شود به‌طوری‌که به‌ازای هر دنباله‌ی درخواست و هر ساختار اولیه‌ی دلخواه برای لیست، هزینه‌ی الگوریتم ‎«پ»‎ حداکثر ‎$a$‎ واحد بیش از ‎$c$‎ برابرِ هزینه‌ی الگوریتم ‎«ب»‎ باشد. یعنی

1. ‎نشان دهید ثابت ‎$c$‎ وجود ندارد که الگوریتم ‎«الف» $c$-‎رقابتی باشد.
2. اگر الگوریتم برخطی $c$-‎‎رقابتی باشد (که ‎$c$‎ ثابت است)، اثبات کنید ‎$c\geq 2$‎ می‌باشد.

• سوال بعد
• سوال قبل