التعقيد الحسابي

في علوم الكمبيوتر، التعقيد الحسابي أو كما يعرف أيضا تعقيد الخوارزمية بأنه  كمية أو مقدار الموارد المطلوبة لتشغيلها. يركز التعقيد الحسابي بشكل خاص على وقت الحساب (الذي يُقَاسُ عموماً بعدد العمليات الأولية المطلوبة) ومتطلبات تخزين الذاكرة. تعقيد المشكلة هو تعقيد أفضل الخوارزميات التي تسمح بحل المشكلة.

يطلق على دراسة تعقيد الخوارزميات المعطاة بشكل صريح تحليل الخوارزميات، بينما يطلق على دراسة تعقيد المشكلات نظرية التعقيد الحسابي. يرتبط كلا المجالين ارتباطًا وثيقًا، حيث أن تعقيد الخوارزمية دائمًا ما يكون حدًا أعلى لتعقيد المشكلة التي تحلها هذه الخوارزمية. بالإضافة إلى ذلك، كي تُصَمَّم خوارزميات فعالة، غالبًا ما يكون من المهم بشكل جوهري القيام  بمقارنة مدى تعقيد خوارزمية معينة مع مدى تعقيد المشكلة التي يتوجب حلها. وعلاوة على ذلك، في معظم الحالات، الشيء الوحيد المعلوم عن مدى تعقيد المشكلة هو أنها أقل من تعقيد الخوارزميات المعروفة الأكثر كفاءة. ولذلك، هناك امتزاج عميق بين تحليل الخوارزميات ونظرية التعقيد.

بما أن مقدار الموارد المطلوبة لتشغيل خوارزمية يختلف عمومًا باختلاف حجم الإدخال، يُعبر عن التعقيد عادةً دالةً  حيث  هو حجم الإدخال و  إما التعقيد الأسوأ (الحد الأقصى لمقدار الموارد المطلوبة على جميع المدخلات بالحجم  ) أو تعقيد الحالة المتوسطة (متوسط كمية الموارد على جميع المدخلات بالحجم  ). يعبر  عن التعقيد الزمني عمومًا بعدد العمليات الأولية المطلوبة على مُدخل بالحجم  ، حيث يُفترض أن العمليات الأولية تستغرق مقدارًا ثابتًا من الوقت على جهاز كمبيوتر معين ولا تتغير إلا بعامل ثابت عند تشغيلها على جهاز كمبيوتر مختلف. يتم التعبير عن التعقيد الفضائي بشكل عام على أنه مقدار الذاكرة التي تتطلبها الخوارزمية عند إدخال الحجم  .

 الموارد 

 الوقت 
المورد الأشد أهمية و شيوعا هو الوقت. حين يُسْتَخْدَم "التعقيد" بدون شروط، فهذا يعني بشكل عام تعقيد الوقت.

لا يمكن استخدام وحدات الوقت المعتادة (الثواني والدقائق والساعات) في نظرية التعقيد نظرا لأنها تعتمد بشكل أساسي على اختيار جهاز كمبيوتر معين وكذلك على تطور التكنولوجيا.
مثالا على ذلك، باستطاعة الكمبيوتر اليوم تنفيذ خوارزمية أسرع بكثير من كمبيوتر الستينيات؛ على الرغم من أنها لا تعد سمة أاسية للخوارزمية ولكنها نتيجة طبيعية للتقدم التكنولوجي في أجهزة الكمبيوتر. تحاول نظرية التعقيد إلى تحديد متطلبات الوقت الجوهرية للخوارزميات، أي القيود الزمنية الأساسية التي قد تضعها الخوارزمية على أي جهاز كمبيوتر. يُحقق ذلك عن طريق حساب عدد العمليات الأولية التي تُنَفَّذ أثناء الحساب. من المفترض أن تستغرق هذه العمليات وقتًا ثابتًا (أي لا تتأثر بحجم الإدخال) على جهاز معين، وغالبًا ما تسمى الخطوات .

 تعقيد البت 
عامة ما يشير تعقيد البت إلى عدد العمليات على البتات اللازمة لتشغيل الخوارزمية. في معظم نماذج الحساب ، فإنه يساوي التعقيد الزمني حتى عامل ثابت. على أجهزة الكمبيوتر ، يتناسب عدد العمليات المطلوبة على الكلمات الآلية أيضًا مع تعقيد البت. لذا، فإن التعقيد الزمني وتعقيد البت متساويان في النماذج الواقعية للحساب.

 تواصل 
اما فيما يتعلق بفئة الخوارزميات الموزعة التي تنفذ عادة  عن طريق أطراف متعددة متفاعلة،  لذا يعد المورد الأكثر أهمية هو تعقيد الاتصالات. إنه القدر الضروري من التواصل بين الأطراف المنفذة.

تصنيف:نظرية التعقيد الحسابي
تصنيف:تحليل الخوارزميات