۱
subtitle
ارسال: #۱
ابهام در حل مسائل بازگشتی الگوریتم
سلام
لطفا تصویر رو مشاهده بفرمائید:
![[تصویر: 228568_Algorithm_problem.jpg]](https://img.manesht.ir/228568_Algorithm_problem.jpg)
توی این تصویر اگر به قسمت زرد رنگ اش دقت کنید بوسیله ی تغییر متغیر شکل تابع رو بصورت تابع ناهمگن در آوردیم، بعد بجای تابع [tex]f(2^{k})[/tex] تابع [tex]g(k)[/tex] رو قرار دادیم، یعنی در اصل بجای [tex]2^{k}[/tex] نوشتیم [tex]k[/tex]، به همین ترتیب هم بجای [tex]2^{k-1}[/tex] نوشتیم [tex]k-1[/tex]، تا اینجای کار واضحه ولی مشکل من اینجاست، بجای [tex]4^{k}k[/tex] چی باید بنویسیم؟!
خب اگر [tex]2^{k}[/tex] شده باشه k یعنی این متغیر k در تابع f با متغیر k در تایع g فرق داره و طبیعتا نباید [tex]4^{k}k[/tex] هم همون باشه!
تاکید میکنم مشکل من این نیست که نمیتونم مرتبه زمانی این رو بدست بیارم و هدف پیدا کردن مرتبه زمانی این مثال نیست
امیدوارم منظورم رو رسونده باشم و پیشاپیش از اینکه برای این مشکل وقت میگذارید و پاسخ میدید ممنونتون هستم.
لطفا تصویر رو مشاهده بفرمائید:
توی این تصویر اگر به قسمت زرد رنگ اش دقت کنید بوسیله ی تغییر متغیر شکل تابع رو بصورت تابع ناهمگن در آوردیم، بعد بجای تابع [tex]f(2^{k})[/tex] تابع [tex]g(k)[/tex] رو قرار دادیم، یعنی در اصل بجای [tex]2^{k}[/tex] نوشتیم [tex]k[/tex]، به همین ترتیب هم بجای [tex]2^{k-1}[/tex] نوشتیم [tex]k-1[/tex]، تا اینجای کار واضحه ولی مشکل من اینجاست، بجای [tex]4^{k}k[/tex] چی باید بنویسیم؟!
خب اگر [tex]2^{k}[/tex] شده باشه k یعنی این متغیر k در تابع f با متغیر k در تایع g فرق داره و طبیعتا نباید [tex]4^{k}k[/tex] هم همون باشه!
تاکید میکنم مشکل من این نیست که نمیتونم مرتبه زمانی این رو بدست بیارم و هدف پیدا کردن مرتبه زمانی این مثال نیست
امیدوارم منظورم رو رسونده باشم و پیشاپیش از اینکه برای این مشکل وقت میگذارید و پاسخ میدید ممنونتون هستم.
۱
ارسال: #۲
RE: ابهام در حل مسائل بازگشتی الگوریتم
سلام
منم قبلا به یه همچین مشکلی خوردم و دلیلش اینه که ما دوبار تغییر متغیر نمیدیم بلکه یه عمل rename داریم انجام میدیم. مطابق کتاب clrs :
اول بگیرید m = lg n بعد اینو بزارید توی رابطمون، بعد داریم یه همچین فرمی [tex]f(2^ k) - f(2 ^{k-1}) = 4^kk[/tex] حالا اینجا [tex]f(2^ k) = S(m)[/tex] بگذارید، مهم اینه که ما تغییر متغیر نمیدیم! فقط تغییر نام داریم. واصلا کاری به سمت راست عبارت نداریم. به کتاب clrs ویراش ۳ صفحه ۸۶ انگلیسی مراجعه کنید.
منم قبلا به یه همچین مشکلی خوردم و دلیلش اینه که ما دوبار تغییر متغیر نمیدیم بلکه یه عمل rename داریم انجام میدیم. مطابق کتاب clrs :
اول بگیرید m = lg n بعد اینو بزارید توی رابطمون، بعد داریم یه همچین فرمی [tex]f(2^ k) - f(2 ^{k-1}) = 4^kk[/tex] حالا اینجا [tex]f(2^ k) = S(m)[/tex] بگذارید، مهم اینه که ما تغییر متغیر نمیدیم! فقط تغییر نام داریم. واصلا کاری به سمت راست عبارت نداریم. به کتاب clrs ویراش ۳ صفحه ۸۶ انگلیسی مراجعه کنید.
۰
ارسال: #۳
RE: ابهام در حل مسائل بازگشتی الگوریتم
سلام. متاسفانه چند وقتیه که من نمی تونم DropBox را load کنم. آیا ممکنه این عکس را در سرور دیگری نیز قرار بدید ؟ ممنونم.
ارسال: #۴
RE: ابهام در حل مسائل بازگشتی الگوریتم
(۱۱ آذر ۱۳۹۲ ۰۳:۵۵ ب.ظ)Morris نوشته شده توسط: سلام. متاسفانه چند وقتیه که من نمی تونم DropBox را load کنم. آیا ممکنه این عکس را در سرور دیگری نیز قرار بدید ؟ ممنونم.سلام آقای موریس
هر تصویری از هر سروری توی مانشت بزارید خودکار میفرستتش روی دراپ باکس
البته درباره مشکلتون توی DropBox که مشکل من هم هست، کافیه توی url کلمه https رو به http تبدیل کنید.
۰
ارسال: #۵
RE: ابهام در حل مسائل بازگشتی الگوریتم
منم خیلی در این زمینه یقین ندارم. نظر من هم مثل Riemann هست
زمانی که ما بجای n عبارت [tex]2^k[/tex] میذاریم یعنی علنا داریم تغییر متغیر انجام میدیم.
ولی زمانی که [tex]f(2^k) = g(k)[/tex] قرار میدیم؛ ما تغییر متغیر انجام نمیدیم بلکه داریم به تعبیری تغییر تابع انجام میدیم و عبارت ناهمگن [tex]k4^k[/tex] تابع حساب نمیشه بلکه یک مقدار ثابت حساب میشه.
زمانی که ما بجای n عبارت [tex]2^k[/tex] میذاریم یعنی علنا داریم تغییر متغیر انجام میدیم.
ولی زمانی که [tex]f(2^k) = g(k)[/tex] قرار میدیم؛ ما تغییر متغیر انجام نمیدیم بلکه داریم به تعبیری تغییر تابع انجام میدیم و عبارت ناهمگن [tex]k4^k[/tex] تابع حساب نمیشه بلکه یک مقدار ثابت حساب میشه.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close