۰
subtitle
ارسال: #۱
ساختمان داده سراسری ۹۵ سوال ۴۷
سلام کسی می دونه این سوال چه جوری حل میشه ؟
۰
ارسال: #۲
RE: ساختمان داده سراسری ۹۵ سوال ۴۷
(۰۷ آبان ۱۳۹۵ ۰۵:۲۰ ب.ظ)mostafaheydar1370 نوشته شده توسط: سلام کسی می دونه این سوال چه جوری حل میشه ؟
[tex]log\ast[/tex] یک عدد یعنی از اون عدد چند بار لگاریتم بگیریم تا بشه ۱/ مثلاً برای ۶۵۵۳۶، یک بار لگاریتم بگیریم میشه ۱۶، بار دیگه بگیریم ۱۶ میشه ۴، سپس ۲ و ۱/ یعنی چهار.
حالا [tex]log\ast (log)[/tex] یعنی اول یکبار لگاریتم بگیریم، بعد وارد تابع [tex]log\ast[/tex] بکنیمش. توو مثال بالا، یعنی به جای ۶۵۵۳۶، عدد ۱۶ رو وارد اون تابع بکنیم که جواب خواهد شد ۳ (۳ مرتبه لگاریتم گرفتن برای ۱ کردن لازم میشه). یعنی عملاً مثل این میمونه که تابع بازگشتی/سلسله‌مراتبی [tex]log\ast[/tex] رو یک بار از قبل انجام دادیم و [tex]k-1[/tex] مرحله مونده. در واقع [tex]log\ast(log(n)) = log\ast(n) - 1[/tex]. پس رشد این تابه مثل هم هست چون عدد ثابت در مقایسه‌ی رشد توابع مهم نیست.
ما اون یکی مورد، یعنی [tex]log(log \ast)[/tex] اومده از تابع [tex]log\ast[/tex] لگاریتم گرفته که قطعاً رشدش رو کم میکنه. مثل این میمونه که شما [tex]n[/tex] رو با [tex]\log(n)[/tex] مقایسه کنید که قطعاً رشد [tex]n[/tex] بیشتر هست.
پس گزاره‌ی سمت راست معادل با همون [tex]log\ast[/tex] شد، گزاره‌ی سمت راست ولی لگاریتمِ [tex]log\ast[/tex]. پس سمت چپی [tex]o[/tex] سمت راستی هست (گزینه‌ی ۴ فقط صدق میکنه).
در مورد ب هم، [tex]\sum_{x=1}^{n} x^{k}[/tex] مثل این میمونه که انتگرال تابع [tex]x^k[/tex] رو از برای x از ۱ تا n به روش مستطیلی با گام‌های [tex]\Delta=1[/tex] حساب کنیم (محاسبات عددی رو نگاه کنید). یعنی
[tex]\sum_{x=1}^{n} x^{k} = \int_{1}^{n} x^k dx = \theta (n^{k+1})[/tex] . در نتیجه برای [tex]\sqrt{i}[/tex] یا همون [tex]i^{\frac{1}{2}}[/tex] جواب میشه [tex]n^{\frac{1}{2}+1}=n\sqrt{n}[/tex]، گزینه‌ی ۴/
ارسال: #۳
RE: ساختمان داده سراسری ۹۵ سوال ۴۷
(۰۷ آبان ۱۳۹۵ ۰۵:۵۳ ب.ظ)Behnam نوشته شده توسط:سنجش گزینه ی ۲ رو گزینه ی صحیح اعلام کرده!(07 آبان ۱۳۹۵ ۰۵:۲۰ ب.ظ)mostafaheydar1370 نوشته شده توسط: سلام کسی می دونه این سوال چه جوری حل میشه ؟
[tex]log\ast[/tex] یک عدد یعنی از اون عدد چند بار لگاریتم بگیریم تا بشه ۱/ مثلاً برای ۶۵۵۳۶، یک بار لگاریتم بگیریم میشه ۱۶، بار دیگه بگیریم ۱۶ میشه ۴، سپس ۲ و ۱/ یعنی چهار.
حالا [tex]log\ast (log)[/tex] یعنی اول یکبار لگاریتم بگیریم، بعد وارد تابع [tex]log\ast[/tex] بکنیمش. توو مثال بالا، یعنی به جای ۶۵۵۳۶، عدد ۱۶ رو وارد اون تابع بکنیم که جواب خواهد شد ۳ (۳ مرتبه لگاریتم گرفتن برای ۱ کردن لازم میشه). یعنی عملاً مثل این میمونه که تابع بازگشتی/سلسله‌مراتبی [tex]log\ast[/tex] رو یک بار از قبل انجام دادیم و [tex]k-1[/tex] مرحله مونده. در واقع [tex]log\ast(log(n)) = log\ast(n) - 1[/tex]. پس رشد این تابه مثل هم هست چون عدد ثابت در مقایسه‌ی رشد توابع مهم نیست.
ما اون یکی مورد، یعنی [tex]log(log \ast)[/tex] اومده از تابع [tex]log\ast[/tex] لگاریتم گرفته که قطعاً رشدش رو کم میکنه. مثل این میمونه که شما [tex]n[/tex] رو با [tex]\log(n)[/tex] مقایسه کنید که قطعاً رشد [tex]n[/tex] بیشتر هست.
پس گزاره‌ی سمت راست معادل با همون [tex]log\ast[/tex] شد، گزاره‌ی سمت راست ولی لگاریتمِ [tex]log\ast[/tex]. پس سمت چپی [tex]o[/tex] سمت راستی هست (گزینه‌ی ۴ فقط صدق میکنه).
در مورد ب هم، [tex]\sum_{x=1}^{n} x^{k}[/tex] مثل این میمونه که انتگرال تابع [tex]x^k[/tex] رو از برای x از ۱ تا n به روش مستطیلی با گام‌های [tex]\Delta=1[/tex] حساب کنیم (محاسبات عددی رو نگاه کنید). یعنی
[tex]\sum_{x=1}^{n} x^{k} = \int_{1}^{n} x^k dx = \theta (n^{k+1})[/tex] . در نتیجه برای [tex]\sqrt{i}[/tex] یا همون [tex]i^{\frac{1}{2}}[/tex] جواب میشه [tex]n^{\frac{1}{2}+1}=n\sqrt{n}[/tex]، گزینه‌ی ۴/
ارسال: #۴
RE: ساختمان داده سراسری ۹۵ سوال ۴۷
ارسال: #۵
RE: ساختمان داده سراسری ۹۵ سوال ۴۷
(۰۷ آبان ۱۳۹۵ ۰۵:۵۳ ب.ظ)Behnam نوشته شده توسط:خیلی ممون بابت پاسخ من برای اینکه حل مسئله سریع تر بشه به صورت نمادی حلش می کنم تا فهمش راحتر بشه(07 آبان ۱۳۹۵ ۰۵:۲۰ ب.ظ)mostafaheydar1370 نوشته شده توسط: سلام کسی می دونه این سوال چه جوری حل میشه ؟
[tex]log\ast[/tex] یک عدد یعنی از اون عدد چند بار لگاریتم بگیریم تا بشه ۱/ مثلاً برای ۶۵۵۳۶، یک بار لگاریتم بگیریم میشه ۱۶، بار دیگه بگیریم ۱۶ میشه ۴، سپس ۲ و ۱/ یعنی چهار.
حالا [tex]log\ast (log)[/tex] یعنی اول یکبار لگاریتم بگیریم، بعد وارد تابع [tex]log\ast[/tex] بکنیمش. توو مثال بالا، یعنی به جای ۶۵۵۳۶، عدد ۱۶ رو وارد اون تابع بکنیم که جواب خواهد شد ۳ (۳ مرتبه لگاریتم گرفتن برای ۱ کردن لازم میشه). یعنی عملاً مثل این میمونه که تابع بازگشتی/سلسله‌مراتبی [tex]log\ast[/tex] رو یک بار از قبل انجام دادیم و [tex]k-1[/tex] مرحله مونده. در واقع [tex]log\ast(log(n)) = log\ast(n) - 1[/tex]. پس رشد این تابه مثل هم هست چون عدد ثابت در مقایسه‌ی رشد توابع مهم نیست.
ما اون یکی مورد، یعنی [tex]log(log \ast)[/tex] اومده از تابع [tex]log\ast[/tex] لگاریتم گرفته که قطعاً رشدش رو کم میکنه. مثل این میمونه که شما [tex]n[/tex] رو با [tex]\log(n)[/tex] مقایسه کنید که قطعاً رشد [tex]n[/tex] بیشتر هست.
پس گزاره‌ی سمت راست معادل با همون [tex]log\ast[/tex] شد، گزاره‌ی سمت راست ولی لگاریتمِ [tex]log\ast[/tex]. پس سمت چپی [tex]o[/tex] سمت راستی هست (گزینه‌ی ۴ فقط صدق میکنه).
در مورد ب هم، [tex]\sum_{x=1}^{n} x^{k}[/tex] مثل این میمونه که انتگرال تابع [tex]x^k[/tex] رو از برای x از ۱ تا n به روش مستطیلی با گام‌های [tex]\Delta=1[/tex] حساب کنیم (محاسبات عددی رو نگاه کنید). یعنی
[tex]\sum_{x=1}^{n} x^{k} = \int_{1}^{n} x^k dx = \theta (n^{k+1})[/tex] . در نتیجه برای [tex]\sqrt{i}[/tex] یا همون [tex]i^{\frac{1}{2}}[/tex] جواب میشه [tex]n^{\frac{1}{2}+1}=n\sqrt{n}[/tex]، گزینه‌ی ۴/
[tex]\log\ast(n)=i\: \&\&\: \log(n)=k\Rightarrow\log\ast(k)=i-1=\log\ast(n)-1\Rightarrow right\: side\: =i-1\&\&left\: side\: =\log(i)\Rightarrow\frac{\log(i)}{i}<1\Rightarrow\log(i)<i\: \Rightarrow\log(i)=o(i)[/tex]
و چون گزینه ی ۴ تنها گزینه ای است که نماد او کوچک رو دارد پس جواب میشه گزینه ی ۴
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close