اين هم از آخرين نماد!
نماد |
اگر براي دو تابع و داشته باشيم:
و
در اين صورت:
در حقيقت مجموعهي اشتراك دو مجموعه ي و ميباشد.
اين نماد در حقيقت اصليترين «نماد پيچيدگي الگوريتم»هاست زيرا در حقيقت ميتوانيم بگوييم اگر:
در اين صورت رشد توابع به يك اندازه است.
براي درك اين مفهوم به توابع زير توجه كنيد
ياداوري - به ياد داشته باشيد كه خيلي وقتها نماد O بهجاي بهكار ميرود!
اگر:
باشد در اينصورت:
و اگر:
باشد در اينصورت:
ميدانيم كه اگر:
باشد در اينصورت هر دو رابطهي بالا برقرار است.
حال m را براي ماكزيمم بگيريد در اينصورت داريم:
| | : |
مفهوم اين رابطه چيست؟ اين رابطه بيان ميدارد كه از جايي به بعد بين ضرايبي از قرار دارد. در حقيقت نرخ رشد مشابه است.