الملك والرياضيات

أُسس ال 2 والنمو الأسّيِش

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