زمان کنونی: ۲۱ آذر ۱۳۹۷, ۰۵:۲۸ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

بهترین زمان برای ساخت یک درخت BST با nکلید و ارتفاع دقیقا n-1

ارسال:
  

Mr.R3ZA پرسیده:

بهترین زمان برای ساخت یک درخت BST با nکلید و ارتفاع دقیقا n-1

با سلام
بهترین زمان برای ساخت یک درخت BST با nکلید و ارتفاع دقیقا n-1 چه مرتبه ای میتونه داشته باشه؟؟؟
باتشکر
نقل قول این ارسال در یک پاسخ

۱
ارسال:
  

Alisalar پاسخ داده:

RE: بهترین زمان برای ساخت یک درخت BST با nکلید و ارتفاع دقیقا n-1

سلام
اگه مقادیر کلیدها صحیح باشند که میشه باکت سورت زدو توی زمان n مرتبشون کرد و توی زمان n هم bst بسازیم
پس داریم تتای n+n که همون n میشه
اگه مقادیر کلیدها صحیح نباشه که کمتر از nlgn نمیشه قطعا مگر اینکه کلیدها از قبل مرتب باشن
منتظر به چالش کشیده شدن هستمSmile
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

عزیز دادخواه پاسخ داده:

RE: بهترین زمان برای ساخت یک درخت BST با nکلید و ارتفاع دقیقا n-1

به نظرم در حالتی که همه کلید ها رو داشته باشیم و بعد inorder کنیم که درست نیست چون در این صورت ارتفاعش لگاریتمی میشه.
اگر کلید ها رو یکی یکی درج کنیم که میشه n*h. که با توجه به اینکه ارتفاع درخت رو n گرفتید پس مرتبه زمانی ان به توان دو میشه.
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

عزیز دادخواه پاسخ داده:

RE: بهترین زمان برای ساخت یک درخت BST با nکلید و ارتفاع دقیقا n-1

ممنونم به نظرم حرف شما درست تره. بله اگه بشه با مرتبه n مرتب کرد مرتبه زمانیش کمتر میشه.
ممنونم از جوابتون.

البته یک نکته رو بگم که ممنون میشم نظرتون رو بگید این روشی که دوستمون گفتند n میشه به نظر من روش غیر عملیه که حتما باید در مرحله اول همه داده ها موجود باشند که بتونیم با مرتبه n مرتبشون کنیم. درسته این حرف؟
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Mr.R3ZA پاسخ داده:

RE: بهترین زمان برای ساخت یک درخت BST با nکلید و ارتفاع دقیقا n-1

من که هنوز متوجه نشدم؟؟
آیا کسی هست که بتونه بهتر توضیح بده؟
نقل قول این ارسال در یک پاسخ

ارسال:
  

Alisalar پاسخ داده:

RE: بهترین زمان برای ساخت یک درخت BST با nکلید و ارتفاع دقیقا n-1

سلام
ساخت bst دو حالت داره
حالت اول اینه که تمام کلیدها رو در ابتدا داشته باشیم یعنی n تا کلید به ما بدن بگن باهاشون bst بساز
حالت دوم اینه که تمام کلیدها رو با هم ندن و به تدریج کلیدها سر و کلشون پیدا بشه (مثل خیلی از کنفرانسها و کلاسها و جلساتی که توی ایران برگزار میشهWink)

در حالت اول کلیدها رو در زمان (O(nlgnمرتب می کنیم ، خوب حالا باید با این کلیدای مرتب شده درخت بسازیم
صورت سوال گفته درخت به ارتفاع n-1 یعنی همون درخت مورب که هر سطحش فقط یه گره داره
کارمون سادس ، کلیدهای مرتب شده رو به ترتیب (صعودی یا نزولیش فرق نمیکنه) زیر هم درج می کنیم که میشه از مرتبه (teta(n
پس کل عملیات شد مرتب سازی + درج گره ها
یعنی (teta(nlgn + n که با روش ماکسیمم گیری برابر میشه با (teta(nlgn
البته اگر مقادیر کلیدها تمامشون اعداد صحیح باشن میشه از روش مرتب سازی bucket sort استفاده کرد که یه روش مرتب سازی غیرمقایسه ای هست و عمل مرتب سازی رو در زمان (teta(n انجام میده که در این صورت میشه bst رو توی زمان (teta(n ایجاد کرد

روش دوم یه کم پیچیدگی داره اجازه بدین بیشتر فکر کنم یا از دوستان بپرسم بعدا پاسخش رو ارسال کنم
طبق معمول منتظر به چالش کشیده شدن هستم
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

Alisalar پاسخ داده:

RE: بهترین زمان برای ساخت یک درخت BST با nکلید و ارتفاع دقیقا n-1

حالت دوم که کلیدها به تدریج از راه میرسند
باید n کلید رو توی bst درج کنیم عمل درج در bst بدین صورته که عنصر مورد نظر رو جستجو می کنیم اگر پیدا شد که نیاز به درج نیست ولی اگر پیدا نشد باید در همون نقطه ای که عمل جستجو به پایان رسیده یه گره جدید ایجاد کنیم و مقدار موردنظر رو توی اون گره قرار بدیم این عمل از مرتبه (O(lgn هست چون درحالت متوسط ارتفاع bst از مرتبه lgn هست و جستجو هم نهایتا به اندازه ارتفاع درخت ، گره ها رو بررسی میکنه
پس درج n گره در حالت متوسط (O(nlgn و در بدترین حالت که گره ها مرتب شده هستند و ارتفاع درخت n-1 هست برابر میشه با n^2
اما اینجا یه مشکلی هست گره ها به تدریج وارد میشن و ممکنه bst هر شکلی پیدا کنه ولی ما باید درختمون مورب باشه پس بعد از هر عمل درج ممکنه لازم باشه بعضی گره ها رو دوران بدیم یعنی (O(n تا دوران داریم که مرتبه اونا رو نمی دونم فقط می دونم هر عمل دوران سه تا اشاره گر رو تغییر میده
اگر هر عمل دوران رو از مرتبه (teta(1 فرض کنیم n تا دوران میشه از مرتبه (teta(n که چون لزوما تمام درج ها به دوران نیاز ندارن داریم (O(n
پس کل عملیات میشه (O(nlgn + n که همون (O(nlgn هست

دوستان اگه نظری درمورد دوران دارن خوشحال میشم راهنمایی کنن
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  بهترین زمان بهینه برای مساله بزرگترین زیر دنباله صعودی(LIS) امیدوار ۳ ۵۳۴ ۱۲ خرداد ۱۳۹۷ ۰۵:۴۳ ق.ظ
آخرین ارسال: Mr.R3ZA
  بهترین زمان برای حل کوله پشتی به روش پویا Mr.R3ZA ۰ ۲۰۲ ۱۲ خرداد ۱۳۹۷ ۰۲:۰۶ ق.ظ
آخرین ارسال: Mr.R3ZA
  چطور میشه هر الگوریتمی را طوری تغییر داد که بهترین زمان اجرای خوبی داشته باشه؟ farid612004 ۱ ۲۷۹ ۱۷ آبان ۱۳۹۶ ۰۴:۱۴ ب.ظ
آخرین ارسال: msour44
  اردر زمانی ومکانی یک درخت mostafaheydar ۰ ۳۴۳ ۲۹ اردیبهشت ۱۳۹۶ ۰۴:۳۲ ق.ظ
آخرین ارسال: mostafaheydar
  سوال در مورد زمان بندی فعالیت ها با مهلت معین sarashahi ۷ ۱,۹۷۳ ۰۶ اردیبهشت ۱۳۹۶ ۰۶:۲۷ ب.ظ
آخرین ارسال: amin noruzi
  ۶۰۰ مساله | درخت قرمز سیاه | ۴۰/۴ | صفحه ۷۷ Happiness.72 ۱ ۳۹۷ ۲۸ اسفند ۱۳۹۵ ۰۳:۱۹ ق.ظ
آخرین ارسال: msour44
  روش های بهبود زمان و فضا در مرتب سازی سریع از طریق کاستن عمق پشته بازگشت shamim1395 ۱ ۴۰۰ ۰۳ بهمن ۱۳۹۵ ۰۲:۲۱ ب.ظ
آخرین ارسال: Saman
  پیچیدگی زمانی به روش ترسیم درخت wskf ۳ ۸۶۲ ۰۷ مهر ۱۳۹۵ ۰۸:۴۷ ب.ظ
آخرین ارسال: wskf
  پیچیدگی زمان اجرا- قدسی dokhtare payiz ۳ ۷۸۰ ۲۹ اردیبهشت ۱۳۹۵ ۱۱:۵۴ ب.ظ
آخرین ارسال: dokhtare payiz
  ابهام در درخت بازگشتی irpersian20 ۱ ۶۲۰ ۱۸ اردیبهشت ۱۳۹۵ ۰۷:۳۶ ب.ظ
آخرین ارسال: fatemeh69

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close