كتب algorithm complexity measurement
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
قياس تعقيد الخوارزمية (معلومة)
لقياس صعوبة مسألة حاسوبية وجب على المرء ان يقيس الوقت اللازم لافضل خوارزمية تحل المسألة، وبشكل عام الوقت قد يرتبط بطول المُدخل وبالتحديد مُدخلات طويلة حتما ستحتاج أكثر وقت للوصول للحل. لذا فان قياس الوقت اللازم لحل مسألة هو دالة بطول المُدخل، وبشكل عام طول المُدخل يكون بالبتات. لذا فان علم التعقيد بالأساس يبحث مدى قابلية توسع الخوارزمية.
فلنفرض أن n هو طول المُدخل حينها الوقت اللازم للخوارزمية يمكن التعبير عنه بواسطة n، وبما أن لكل مُدخل قد يكون الوقت اللازم لحل المسألة مختلف لذا فانه يُأخذ بالاعتبار تعقيد وقت الحالة الأسوأ , (T(n , والذي هو الوقت الأطول الذي ستحتاجه الخوارزمية بالنسبة لكل المدخلات.
إذا كان (T(n متعدد الحدود أي: يوجد ثابت c>0 بحيث أن (T(n)=O(nc حينها نقول أن الخوارزمية وقتها متعددة الحدود (polynomial time algorithm). أطروحة كوبهام تقترح أن مسألة يمكن حلها مع كمية معقولة من الموارد إذا يوجد خوارزمية تحلها بوقت متعدد الحدود.
