برای پیدا کردن یک الگوریتم بهینه٬ در بیشتر موارد میزان افزایش زمان اجرای یک الگوریتم با افزایش اندازه‌ی مسئله مورد توجه ماست.
فرض کنید که سه تا الگوریتم به نامهای P و Q و R داریم که با اندازه ورودیهای مختلف در بدترین شرایط زمان اجرایی طبق جدول زیر دارند:
n P Q R
1 1 5 100
10 1024 500 1000
100 2^100 50,000 10,000
1000 2^1000 5,000,000 100,000
اگر هر کدوم از این الگوریتمها توسط ماشینی که در هر ثانیه یک میلیون <span dir=ltr>(10^6)</span> عمل پایه رو اجرا می‌کند اجرا بشوند٬ داریم:
n P Q R
1 1 µs 5 µs 100 µs
10 1 ms 0.5 ms 1 ms
100 2^70 years 0.05 sec. 0.01 sec.
1000 2^970 years 5 sec. 0.1 sec.
همانطور که می‌بینید٬ بیان میزان رشد زمان بر حسب <span dir=ltr>(2^n, n^2; n) n</span> معنی‌دارتر از بیان آن با فاکتورهای ثابت <span dir=ltr>(1; 5; 100)</span> است.
نماد O
فرض کنید <span dir=ltr>f.N -> R</span> و <span dir=ltr>g.N -> R</span> در این صورت داریم:
f(n) = O(g(n))
این به این معناست که مقادیر n0 و c ای وجود دارند که:
f(n) <= c * g(n)
که
n >= n0
و بر این اساس می‌توانیم زمان اجرای یک الگوریتم را بر حسب اندازه ورودی بیان کنیم.
به عنوان نمونه:- الگوریتمی برای مرتب کردن n عنصر وجود دارد (mergesort) که زمان اجرای آن <span dir=ltr>O(n log n)</span> است.
- الگوریتمی برای ضرب دو عدد n رقمی وجود دارد که زمان اجرای آن <span dir=ltr>O(n^2)</span> است.
- الگوریتمی برای بدست آوردن nامین عدد سری فیبوناچی وجود دارد که زمان اجرای آن <span dir=ltr>O(log n)</span> است.
نماد OM
این نماد برای بیان این مفهوم که یک الگوریتم حداقل نیاز به اجرای تعدادی مرحله دارد بکار می‌رود.
دوباره فرض کنید <span dir=ltr>f.N -> R</span> و <span dir=ltr>g.N -> R</span> در این صورت داریم:
f(n) = OM(g(n))
این به این معناست که مقادیر n0 و c ای وجود دارند که:
f(n) >= c * g(n)
که
n >= n0
نماد THETA
دوباره فرض کنید <span dir=ltr>f.N -> R</span> و <span dir=ltr>g.N -> R</span>
اگر <span dir=ltr>f(n)=O(g(n))</span> و <span dir=ltr>f(n)=OM(g(n))</span> داریم:
f(n) = THETA(g(n))
در اینصورت گفته می‌شود <span dir=ltr>f(n)</span> با تقریب بسیار کمی با <span dir=ltr>g(n)</span> برابر است.
اگر <span dir=ltr>f(n) = THETA(g(n))</span> باشد٬ الگوریتمهایی با زمان اجرای <span dir=ltr>f(n)</span> و <span dir=ltr>g(n)</span> با افزایش n بطور برابر افزایش زمان پیدا می‌کند.
روابط بین نمادهای O و OM
<span dir=ltr>f(n)=O(g(n))</span> اگر و فقط اگر <span dir=ltr>g(n)=OM(f(n))</span>
اگر <span dir=ltr>f(n)=O(g(n))</span> در اینصورت داریم:
f(n) + g(n) = O(g(n))
f(n) + g(n) = OM(g(n))
f(n) * g(n) = O(g(n)^2)
f(n) * g(n) = OM(f(n)^2)
به عنوان نمونه اگر <span dir=ltr>f(n)=10n</span> و <span dir=ltr>g(n)=2n^2</span> باشند:
f(n) = O(g(n))
10n + 2n^2 = O(n^2)
10n + 2n^2 = OM(n^2)
(10n) * (2n^2) = O(n^4)
(10n) * (2n^2) = OM(n^2)
پاسخ با نقل قول