الگوریتم امروز

وبلاگ تخصصی الگوریتم

الگوریتم امروز

وبلاگ تخصصی الگوریتم

وبلاگ علمی و مخصوص مباحث الگوریتمی است.
نظر خصوصی نگذارید چون جواب نمی‌دهم نظر عمومی بگذارید بدون نام هم که باشد همانجا جواب می‌دهم.

بایگانی

کتاب هارپلد (فصل ۲)

سه شنبه, ۲۶ فروردين ۱۳۹۳، ۱۱:۳۱ ق.ظ

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

زمان ساخت درخت از اینجا n log phi به دست می‌آید. (phi = نسبت قطر به عرض)

درخت فشرده

برای رسیدن به زمان لگاریتمی بر حسب n باید از مسأله فصل قبل استفاده کنیم و توری مناسب را بسازیم. با این کار اندازه خانه‌ای که باید نقاط را بر حسب آن به دو قسمت تقسیم کنیم به دست می‌آید. ثابت می‌شود که این تقسیم نقاط را تقریبا نصف می‌کند.

*درخت چهارتایی فشرده برای مکان یابی نقطه

جستجوی دودویی روی عمق درخت

*

موافقین ۰ مخالفین ۰ ۹۳/۰۱/۲۶
سپیده آقاملائی

نظرات  (۰)

هیچ نظری هنوز ثبت نشده است

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی