رتبه‌بندی لیست (الگوریتم‌های داده‌های حجیم-قسمت ۱)

فرض کنید یک لیست پیوندی داریم که اینجا به معنی این است که هر گره یک اندیس (یا مثل آن) دارد که نشان می‌دهد که عنصر بعدی‌اش کدام است و یک مقدار دارد که می‌توانیم آن را با بقیه مقایسه کنیم. حالا هدف این است که به دست بیاوریم که هر عنصر هر گره چندمین عنصر لیست است.

معمولی هر کردن مسأله به تعداد عناصر عمل ورودی-خروجی لازم دارد. پس به جای این کار، سعی می‌کنیم زیرمسأله برای آن به دست بیاوریم. برای این کار، یک مجموعه‌ی مستقل پیدا می‌کنیم و آن را حذف می‌کنیم و رتبه‌ی آن را به عنصر بعدی‌اش می‌دهیم. چون هیچ دو تای متوالی در این مجموعه نیستند مشکلی در رتبه‌ها به وجود نمی‌آید و برای اینکه تعداد عناصری که حذف می‌کنیم تأثیری روی رتبه‌هایی که حساب می‌کنیم نداشته باشد، تعدادشان را به بعدی می‌دهیم.

حالا برای به دست آوردن مجموعه‌ی مستقل، چون یک لیست است اگر همین طوری حریصانه حساب کنیم، به یک مجموعه‌ی مستقل با n/3 رأس می‌رسیم. برای ساختنش هم کافی است یک فایل بسازیم و هر بار عنصر بعدی (و احتمالاً قبلی؟) هر عنصر را اضافه کنیم. حالا رأس بعدی را که انتخاب می‌کنیم اول چک می‌کنیم در فایل آنهایی که همسایه‌شان قبلاً انتخاب شده نباشد.

T(N) = T(2/3N)+O(Sort(N)) (N>M)

T(N) = N/B (N<= M)

==> T(N) = O(Sort(N))