برای هر مساله میتوان چندین الگوریتم نوشت، اما کدام الگوریتم گزینه مناسب تری برای پیاده سازی است؟ در این جلسه در مورد پیچیدگی زمانی و مقایسه آهنگ رشد توابع صحبت شده است. بعد از مشاهده ویدیو چند نکته کاربردی که در ویدیو به آن پرداخته نشده است بیان می‌شود و چند تمرین نیز ارائه می‌شود.

مشاهده این آموزش در آپارات

تمرین و نکات تکمیلی جلسه اول درس ساختمان داده

1- کدام یک از گزاره های زیر درست هستند؟

\\\\ \texrm{(1)}\hspace{ 0.5 in}\displaystyle{3n^2 2^n + 5nlog(n) \in o(n^2 2^n)} \\\\ \texrm{(2)}\hspace{ 0.5 in}\displaystyle{n! \in \omega(nlog(n)) } \\\\ \texrm{(3)}\hspace{ 0.5 in}\displaystyle{n^2log(n) \in \theta(n(log(n))^2) } \\\\ \texrm{(4)}\hspace{ 0.5 in}\displaystyle{n^2 \in O(\frac{n^2}{log(n)})} \\\\ \texrm{(5)}\hspace{ 0.5 in}\displaystyle{e^{c\sqrt(n)} = \omega(e^{\sqrt(n)}) \, c \geq 0 } \\\\ \texrm{(6)}\hspace{ 0.5 in}\displaystyle{n^2 = o(nlog(n)) } \\\\ \texrm{(7)}\hspace{ 0.5 in}\displaystyle{n = o(nlog(n)) } \\\\ \texrm{(8)}\hspace{ 0.5 in}\displaystyle{n^2 = \Omega(nlog(n)) }

نکات:

1- با توجه به رابطه زیر
n^{\log_ba} = a^{\log_bn}

می‌توان گفت که:
n = 2 ^ {log(n)}

2- در لگاریتم این ویژگی را داریم:
\log_ba^c = c \log_ba

3- اگر بخواهیم آهنگ رشد دو تابع زیر را با هم مقایسه کنیم

f(n) = n^ 3 , g(n) = \log(n) ^ {\log(n)}

می‌توانیم از دو تابع log بگیریم، و مقایسه را روی لگاریتم این دو تابع انجام دهیم با توجه به نکته شماره ۲ داریم:

\log(f(n)) = 3 \log(n) , \log(g(n)) = \log(n) * \log(\log(n))
بدیهی است که آهنگ رشد g از f بیشتر است.

2- در انتهای ویدیوی جلسه اول، ترتیب رشد چند تابع مهم بیان شد. در لیست زیر چند تابع جدید مشاهده می‌کنید. این توابع را به ترتیب رشد مرتب کنید:

    \[ n^{\log(n)} , \log(n) ^{\log(n)}, 2^n, n^3, 4^{\log(n)},n!,n^2^n,n^n,\log(n!) \]

خواندن این مطالب را از دست ندهید:

  1. جلسه دوم ساختمان داده؛تحلیل الگوریتم ترتیبی
  2. جلسه ششم ساختمان داده؛ لیست پیوندی
  3. جلسه چهارم ساختمان داده؛ پشته ، صف و صف حلقوی
  4. جلسه هفتم ساختمان داده، لیست پیوندی – ادامه
  5. جلسه دهم ساختمان داده، max heap
  6. جلسه نهم ساختمان داده، پیمایش درخت
  7. جلسه هشتم ساختمان داده، درخت (مفاهیم اولیه)
  8. جلسه یازدهم ساختمان داده؛ درخت دودویی جستجو
  9. نمونه سوالات ساختمان داده – 36 سوال
  10. معرفی دوره رایگان آموزش ساختمان داده
  11. جلسه پنجم، کاربرد پشته
  12. آموزش C++ با رویکرد حل مساله
  13. جلسه 4 – تابع در سی پلاس پلاس
  14. نقشه راه برنامه نویسی اندروید
  15. جلسه 12 – تخصیص حافظه پویا در c++