روابط بازگشتی و تحلیل مجانبی

فرض کنید T(x) = ۲T(x/۲) + ۸/۹T(۳x/۴) + θ((x^۲)/(log x)) . دراین‌صورت کدام مورد درست است؟

تابع بازگشتی زیر را در نظر بگیرید: int f(int n) if(n == ۰ n == ۱) return (n + ۱); else if (n == ۲) return ۴; return (f(n-۱) + ۲ f(n-۲) + f(n-۳)); برای n ≥ 3 ، کدام گزینه بهترین کاندید برای f(n) است؟

فرض کنید که در الگوریتم مرتب‌سازی سریع برای انتخاب محور از میان n عنصر آرایه 2⌊ log n⌋ + 1 عنصر اولیه را انتخاب کنیم و با الگوریتم مرتب‌سازی درجی آنها را مرتب کنیم. عنصر میانه این تعداد عنصر مرتب را…

فرض کنید f(n) = n و g(n) = n^((۱+sin n)) ، که n یک عدد صحیح مثبت است. کدام‌یک از گزاره‌های زیر درست است؟ I. f(n) = O(g(n)) II. f(n) = Ω(g(n))

مرتبه زمانی الگوریتم زیر کدام است؟ for(i = ۱ ; i <= n ; i++) for(j = ۱ ; j <= ⌊n/i⌋ ; j++) S.O. ...

یک الگوریتم یک آرایه دوبعدی n × n را به‌عنوان ورودی دریافت می‌کند و زمان اجرای آن برحسب n عبارت است از T(n) = O(n log n) ، زمان الگوریتم برحسب اندازه ورودی m = n^۲ کدام است؟

فرض کنید برای حل یک مسئله باید از بین چهار الگوریتم انتخاب کنید. کدام یک ارجحیت دارد؟

الگوریتم مرتب‌سازی ادغام (Megesort) را درنظر بگیرید. به‌جای اینکه آرایه ورودی را به دو قسمت تقریباً مساوی تقسیم کنیم، آن را به m بخش تقسیم می‌کنیم که لزوماً مساوی نیستند (m یک ثابت است.) سپس به‌صورت…

کدام‌یک از روابط بازگشتی زیر را نمی‌توان مستقیماً با قضیه اصلی حل کرد؟

در کدام مورد، توابع به‌ترتیب صعودی (و نه اکیداً صعودی) بر مبنای رشد تابع از سمت چپ به راست، مرتب شده‌اند؟

آرایه A شامل n عنصر داده شده است. عنصری از آرایه که حافظ بیش از n/2 بار تکرار شده باشد را یک عضو پرتکرار می‌نامیم. می‌خواهیم در آرایه A یک عضو پرتکرار را در صورت وجود پیدا کنیم. در این کار از یک روش…

کدام گزینه مرتبه رابطه بازگشتی T(n) = 2T(⌊√n⌋) + log n را نشان می‌دهد؟

در گونه‌ای از مرتب‌سازی سریع، برای انتخاب محور از میان n عنصر ۲√n+۱ عنصر اول آرایه را انتخاب می‌کنیم و با یک الگوریتم ساده مانند مرتب‌سازی درجی آن را مرتب می‌کنیم. عنصر میانه این تعداد عنصر مرتب را…

کاوشگری روی سیاره‌ای ناشناخته، سطح را به ۱۶ بخش تقسیم می‌کند. او می‌خواهد بداند کدام بخش بیشترین میزان ماده معدنی دارد. الگوریتم او ابتدا هر بخش را به دو نیمه تقسیم می‌کند، مقدار هر نیمه را می‌سنجد و…