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

مرتبه زمانی مرتب سازی توپولوژیک از روشی دیگر

ارسال:
  

Ametrine پرسیده:

مرتبه زمانی مرتب سازی توپولوژیک از روشی دیگر

تو کتاب های پارسه و مدرسان یه روش دیگه هم علاوه بر استفاده از DFS توضیح داده شده.
تو هر کتاب مرتبه ی این روش رو متفاوت نوشته!
کدوم درسته؟

الگوریتم اینه:
Find a node v with no incoming edges and order it first
Delete v from G
Recursively compute a topological ordering of G-(v)
and append this order after v


مدرسان : [tex]O(V^2)[/tex]
پارسه : [tex]O(V E)[/tex]
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Pakniat پاسخ داده:

RE: مرتبه زمانی مرتب سازی توپولوژیک از روشی دیگر

برای بدست آوردن ترتیب توپولوژیکی عناصر ابتدا DFS رو یکبار برای بدست آوردن Finishing time گره ها اجرا کن
بعد بر اساس ماکزیمم مقدار finishing time باید عناصر رو به ترتیب در یک صف قرار بدی
بعد از ابتدای صف عناصر رو انتخاب کن و ترتیب توپولوژیکی گراف بدست میاد
زمان این روال ضریب ثابتی از اجرای DFS هست
نقل قول این ارسال در یک پاسخ

ارسال:
  

Ametrine پاسخ داده:

RE: مرتبه زمانی مرتب سازی توپولوژیک از روشی دیگر

(۲۹ آبان ۱۳۹۳ ۰۸:۴۴ ب.ظ)Pakniat نوشته شده توسط:  برای بدست آوردن ترتیب توپولوژیکی عناصر ابتدا DFS رو یکبار برای بدست آوردن Finishing time گره ها اجرا کن
بعد بر اساس ماکزیمم مقدار finishing time باید عناصر رو به ترتیب در یک صف قرار بدی
بعد از ابتدای صف عناصر رو انتخاب کن و ترتیب توپولوژیکی گراف بدست میاد
زمان این روال ضریب ثابتی از اجرای DFS هست
بله، این الگوریتم اصلی هست.
اینو میدونم.
منظورم مرتبه ی الگوریتمی هست که نوشتم.
این الگوریتم اینجوریه که میاد گره ای رو که درجه ورودیش صفر هست رو پیدا میکنه و حذف میکنه و.....
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

ldns0098 پاسخ داده:

RE: مرتبه زمانی مرتب سازی توپولوژیک از روشی دیگر

(۲۹ آبان ۱۳۹۳ ۰۳:۱۳ ب.ظ)Ametrine نوشته شده توسط:  تو کتاب های پارسه و مدرسان یه روش دیگه هم علاوه بر استفاده از DFS توضیح داده شده.
تو هر کتاب مرتبه ی این روش رو متفاوت نوشته!
کدوم درسته؟
مدرسان : [tex]O(V^2)[/tex]
پارسه : [tex]O(V E)[/tex]

فک کنم یکیشون بر حسب ماتریس مجاورت گفته یکی دیگه بر حسب لیست مجاورتی.
( O(v+e نباید باشه، چون پیچیدگی dfs تتا هستش نه O
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Exclamation سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ Azadam ۶ ۴,۹۳۶ ۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ
آخرین ارسال: Soldier's life
  پکیج آموزشی طراحی وب + فارسی سازی وردپرس + سئو Happiness.72 ۶ ۶,۹۱۸ ۱۸ بهمن ۱۳۹۹ ۰۱:۱۵ ب.ظ
آخرین ارسال: saqarmoshtaq
  مرتب سازی سریع تصادفی چیست؟ Xzrix ۰ ۱,۶۱۹ ۱۴ آذر ۱۳۹۹ ۰۷:۲۲ ب.ظ
آخرین ارسال: Xzrix
  شبیه سازی مقاله Q-Learning kadoos ۱۶ ۱۷,۵۲۱ ۲۵ آبان ۱۳۹۹ ۰۹:۱۹ ب.ظ
آخرین ارسال: nasim.nasim۱
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۳۹۲ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  مرتبه شبه کد rad.bahar ۱ ۲,۳۴۸ ۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ
آخرین ارسال: BBumir
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۲۳,۰۶۲ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda
  مرتبه زمانی Sanazzz ۱۷ ۲۱,۶۵۲ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ
آخرین ارسال: mohsentafresh
  کتاب شبیه سازی آمنت omnet++ berkeley ۱ ۴,۲۲۱ ۰۴ اردیبهشت ۱۳۹۹ ۱۲:۳۳ ق.ظ
آخرین ارسال: محمد رستمی
  پیچیدگی زمانی اکشن های قابل اعمال در یک وضعیت اsepid8994 ۰ ۱,۷۹۴ ۲۹ اسفند ۱۳۹۸ ۱۲:۵۱ ب.ظ
آخرین ارسال: اsepid8994

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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