تحلیل پیچیدگی زمانی

تحلیل پیچیدگی زمانی

هنگامی که کارایی الگوریتم ها را بر حسب زمان تحلیل می کنیم، تعداد چرخه های واقعی CPU را تعیین نمی کنیم، زیرا این به کامپیوتر خاصی که الگوریتم روی آن اجرا می شود، بستگی دارد. به علاوه حتی نمی خواهیم تک تک دستورهای اجرا شده را شمارش کنیم، زیرا تعداد دستورها به نوع زبان برنامه نویسی که الگوریتم توسط آن پیاده سازی می شود و نحوه نوشتن برنامه، بستگی دارد. در عوض ، به معیاری نیاز داریم که مستقل از کامپیوتر ، زبان برنامه نویسیی، برنامه نویسی و خلاصه همه جزئیات الگوریتم از قبیل افزایش اندیس حلقه ها و غیره باشد.
تحلیل پیچیدگی زمانی  یک الگوریتم عبارت از تعیین تعداد دفعاتی است که عمل اصلی  به ازای هر مقدار از اندازه ورودی انجام می شود.گرچه نمی خواهیم  به جزئیات نحوه پیاده سازی الگوریتم ها بپردازیم، معمولا فرض می کنیم عمل اصلی  با حداکثر کارایی ممکن انجام شود. برای مثال، فرض کنیم  الگوریتم طوری پیاده سازی شود که در هر گذر از حلقه while، مقایسه فقط یکبار انجام شود. به این ترتیب، کارآمدترین پیاده سازی از عمل اصلی را تحلیل می کنیم.
هیچ قاعده سهل و صریحی برای انتخاب عملل اصلی وجود ندارد. این کار معمولا سبر اثر تجربه و داوری درست صورت می پذیرد. همانطرو که گفته شده، معمولا  دستوراتی را که ساختار کنترلی  را تشکیل می دهند، در نظر نمی گیریم.
گاهی ممکن است بخواهیم دو عمل اصلی متفاوت را در نظر بگیریم. برای مثال، در الگوریتمی که مرتب سازی را از طریق مقایسه کلید ها انجام می دهد، غالبا دستور مقایسه و دستور انتساب را به هر یک به تنهایی  به عنوان عمل اصلی در نظر می گیریم. منظور این نیست که دو دستور به همراه یکدیگر، عمل اصلی را تشکیل می دهد، بلکه دو عمل اصلی را در نظر می گیریم . منظور این نیست که دو دستور به همراه یکدیگر ، عمل اصلی را تشکیل می دهند، بلکه دو عمل اصلی متمایز داریم، که یکی دستور مقایسه و دیگری دستور انتساب است.