معنی یک عبارت ریاضی را میخواهم
Polynomial time
در اینجا time به چه معنی است
در متن حرفی از زمان گفته نشده
٢ پاسخ
در اینجا time به معنای مرتبه زمانی است.
با توجه به متنی که گذاشتین به نظر میاد که مربوط به الگوریتم های مسیریابی در شبکه های کامپیوتری باشه. اتفاقا اگر دقت کنین ابتدای همین پاراگرافی که مشخص کردین صراحتا در مورد زمان [طی شده توسط] الگوریتم ها صحبت کرده (Psudopolynomial time) و به طور کل توی این پاراگراف داره در مورد پیچیدگی زمانی الگوریتم ها توضیح میده(Time complexity ) و این که در پایان فصل الگوریتم هایی معرفی میکنه که مسئله ی کوتاه ترین مسیر روی گراف رو با پیچیدگی زمانی کمتری انجام بدن.
عبارت polynomial هم به معنای چند جمله ای هست که اگر به مثال ها دقت کنین مرتبه زمانی الگوریتم ها همه از مرتبه های چند جمله ای جبری بر حسب n هستند ( nm برای مثال ).
پس عبارت polynomial-time یعنی از مرتبه ی زمانی چند جمله ای ( این برداشت و ترجمه مختص مبحث الگوریتم ها در زمینه علم کامپیوتر هستش، تعمیم نمیدم به همه ی متن ها!).
در عبارت "Polynomial time"، "time" به معنای "زمان" است. این عبارت، به یک نوع از زمان‌بندی الگوریتم‌های محاسباتی اشاره دارد.
الگوریتم‌های محاسباتی، معمولاً با یک تابع زمان‌بندی توصیف می‌شوند. این تابع، نشان می‌دهد که زمان اجرای الگوریتم، با توجه به اندازه‌ی ورودی، چگونه تغییر می‌کند.
در عبارت "Polynomial time"، "polynomial" به معنای "چندجمله‌ای" است. بنابراین، یک الگوریتم با زمان چندجمله‌ای، الگوریتمی است که زمان اجرای آن، با یک چندجمله‌ای از اندازه‌ی ورودی متناسب است.
به عنوان مثال، الگوریتم مرتب‌سازی سریع، یک الگوریتم با زمان چندجمله‌ای است. زمان اجرای این الگوریتم، با یک چندجمله‌ای از درجه‌ی 2 از اندازه‌ی ورودی متناسب است.
در نظریه پیچیدگی محاسباتی، کلاس P، شامل تمام مسائل تصمیمی است که می‌توانند با یک الگوریتم با زمان چندجمله‌ای حل شوند.
بنابراین، عبارت "Polynomial time" به یک نوع از زمان‌بندی الگوریتم‌های محاسباتی اشاره دارد که در آن، زمان اجرای الگوریتم، با یک چندجمله‌ای از اندازه‌ی ورودی متناسب است.
بسیار متشکرم ، با توضیحات کاملی که دادید جواب یه سوال دیگرم را هم گرفتم ، که در مورد پیچیدگی محاسباتی بود ، ممنون
فقط جسارتا از اندازه و ورودی که فرمودید رو متوجه نشدم ، از اندازه ورودی یعنی چی ؟
پاسخ شما
سلام و درود
بسیار عالی ، ممنونم دوست عزیز، سپاس بیکران از شما و آبادیس