مقارنة منشار التعقيد

Question

لماذا هو الحد الأدنى للتعقيد زمنيا من خوارزميات الفرز القائمة على المقارنة O (N LOG N)؟

Answer 1

http://en.wikipedia.org/wiki/comparison_sort#number_of_comparisons_required_to_sort_a_list.

الإجابات التي السؤال بشكل جيد للغاية، كما أعتقد.

Answer 2

باختصار، لأنك يجب أن ننظر إلى كل عنصر وهو O (ن). لكل من تلك العناصر التي تنظر إليها، يجب عليك معرفة ما إذا كان ذلك بالترتيب الصحيح، وهو في أفضل حالا (سجل ن) (بحث ثنائي على سبيل المثال). لذلك يصبح Sum Net O (N Log N)