الگوریتم های موثر برای رتبه بندی مکانی

سری های زمانی می تواند به عنوان یک توالی رتبه بندی ارائه شود که فراز و نشیب ها با گذر زمان را نشان می دهد. در برخی از مواردکاربردی، یک نفر ممکن است بخواهد مسیر در دوره زمانی خاص را کشف یا آن را برای یک دوره زمانی جستجو کند. ما سهمشکل عمده را طبقه بندی کردیم: مشکل رتبه بندی مکانی، توالی رتبه بندی مکانی و تطبیق توالی رتبه بندی. دو مورد اول بهبررسی رتبه بندیها در یک بخش از توالی زمان می پردازد و مورد آخر به جستجوی موقعیت های تطبیق در سلسله مراتب جستجواشاره دارد. در تمام مشکلات فوق الذکر، ما الگوریتم های گوناگون را با استفاده از ساختمان داده ای درختی شکل اصلاح شده ارائه میکنیم. ایجاد ساختمان بخشها زمان و فضا نیاز ندارد (N .0(n log n طول توالی رتبه بندی هدف است. زمان جستجو سه الگوریتم (o(k), (o(log k و (o(n log k هستند. K اندازه توالی جستجو است.

Keywords:

ساختمان داده ها , رتبه بندی ترتیبی , بخش درختان , شیوه جزء به جزء , تطبیق رشته