(۰۸ آبان ۱۳۹۵ ۱۲:۱۷ ب.ظ)Flora نوشته شده توسط:  سلام دوستان
میشه این سوال ها رو با راه حل،حلشون کنید؟

سلام

در اولی، اون حالت‌های خاص که در نظر گرفته نمی‌شوند. اصلش حلقه هست. در حلقه هم ممکن هست همون اولش، یعنی به ازای i=3، باقی‌مونده‌ی n به i صفر بشه، مثلاً n=90000000 باشه. ولی باز بدترین حالت باید در نظر گرفت بشه. برای اینکه $i^2<n$ باشه، i باید $\sqrt{n}$ تا جلو بره. البته چون اینجا i = i + 2 میشه، باید $\frac{\sqrt{n}}{2}$ جلو بره که مهم نیست و مرتبه‌شون همون $\theta(\sqrt{n})$ هست. دقیق‌ترش میشه $\frac{\sqrt{n}}{2}-3$ چون اولش از ۳ شروع می‌شه (و ۳ گام رفته جلو).

دومی هم باز راحت هست چون حلقه‌ی داخلی، مستقل از حلقه‌ی بیرونی هست. یعنی j هر بار تا n میره (به جای اینکه مثلاً تا i بره که نیاز به سیگما یا روش‌های دیگه باشه). متغیر i هر بار ضربدر ۲ میشه تا وقتی که به n برسه، پس میشه $\log(n)$ بار. j هم که هر بار از ۱ تا n میره، پس مرتبه‌ی کلی میشه $n\cdot\log(n)$. اگر متغیر حلقه‌ی داخلی به متغیر حلقه‌ی بیرونی ربط داشت (مثلا j هر بار تا i می‌رفت) نمیشد به این راحتی ضرب کرد و باید از سیگما استفاده بشه مثلاً.

در سومی هم متغیر حلقه‌ها مستقل هستند، اولی n تا گام داره و دومی $\log(n)$ تا. یعنی به ازای هر i، دومی $\log(n)$ تا دستور اجرا می‌کنه. بنابراین مرتبه مثل بالایی میشه $n\cdot\log(n)$