سلام دوستان...راستش از پیچیدگی زمانی تا یه جاهایی سر در میارم اما مثلا این موضوع رو درک نمیکنم که چرا در بعضی الگوریتم ها تعداد تکرار عمل اصلی رو ضرب در هم میکنیم (مثل ضرب ماتریس n x n که میشه n به توان ۳!) یا مثلا الگوریتم مرتب سازی تعویضی که در آخر مجموع تکرار عمل اصلی میشه جواب ما ! یعنی باید ۱+۲+۳+...+(n-1) رو با هم جمع کنیم؟ این جمع ضرب ها رو از کجا باید متوجه شد! تو هردو حلقه for داریم! گیج شدم !!
در ضرب ماتریسها [tex]n^2[/tex] درایه رو در هم ضرب می کنیم.ضمنا هر درایه ماتریس حاصل نتیجه ضرب یک سطر در یک ستون است که مرتبه زمانی اش [tex]n[/tex] است. [tex]n[/tex] عضو متناظر در هم ضرب میشون و با هم جمع میشوند بخاطر همین مرتبه اش [tex]n[/tex] است.
ضمنا ماتریس نهایی [tex]n^2[/tex] درایه دارد پس مرتبه زمانی برابر است با [tex]n^2\times n=n^3[/tex]
شما برای پیدا کردن مرتبه زمانی باید اعمال اصلی رو پیدا کنید و تکرار اونها روو بررسی کنید.
وقتی تعداد تکرار حلقه‌های داخلی متغیره، به‌ناچار، از جمع استفاده میکنیم (دقت دارید که ضرب عددی در n برابر است با n بار جمع عدد با خودش؛ حالا این عدد ما ثابت نیست و متغیره، پس از ضرب استفاده نمی‌کنیم).