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

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

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

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

الموارد[عدل]

الوقت[عدل]

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

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

تعقيد البت[عدل]

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

تواصل[عدل]

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