تالار گفتمان مانشت

درود
پیچیدگی نمایی چیست ؟ از کجا بدونیم یک الگوریتم میتوان به صورت نمایی اجرا کرد یا نه؟ کاربرد کجاست به غیر از جستجو ! تفاوتش با لگاریتمی چیه؟

(11 فروردین 1394 10:27 ب.ظ)Riemann نوشته شده توسط: [ -> ]تفاوت که خیلیه ! مثلا الگوریتم سیمپلکس پیچیدگی نمایی داره ولی توی صنعت استفاده میشه! تفاوتشون توی زمان رسیدن به پاسخ هست !

فرض کنید یک مساله با سایز ورودی n دارید اگر در مرتبه اجراش توانی از n ظاهر بشه مثلا [tex]2^{\: n}[/tex] بشه مرتبا اجراش اون وقت پیچیدگی نمایی داره. اصولا الگوریتمی که پیچیدگی نمایی داره مورد استفاده قرار نمیگیره(به دلیل زمان اجرای بالا) مگر این که سایز ورودی کوچیک باشه یا این که به صورت expected پیچیدگیش کمتر از upper bound اون باشه

مثلا تو درس الگوریتم موازی ما داریم که توابع نمایی زمان اجراش کمتر تا خطی .مثال جستجو
خیلی برام مبهمه که بیچدگی نمایی چی هست ! به چه الگوریتم های میگن بیچدگی نمایی داره