ارتباك تعقيد الوقت

Question

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

ما لا أفهمه هو ما يسمح للعملية الداخلية مثل set() أن تكون أسرع بكثير من العملية الخارجية لخوارزمية اللغة.لا يزال يتعين إجراء الفحص، أليس كذلك؟

Answer 1

يمكنك القيام بذلك في O (n) بأي لغة، كما هو:

# Get min and max values O(n).

min = oldList[0]
max = oldList[0]
for i = 1 to oldList.size() - 1:
    if oldList[i] < min:
        min = oldList[i]
    if oldList[i] > max:
        max = oldList[i]

# Initialise boolean list O(n)

isInList = new boolean[max - min + 1]
for i = min to max:
    isInList[i] = false

# Change booleans for values in old list O(n)

for i = 0 to oldList.size() - 1:
    isInList[oldList[i] - min] = true

# Create new list from booleans O(n) (or O(1) based on integer range).

newList = []
for i = min to max:
    if isInList[i - min]:
        newList.append (i)

أنا أفترض هنا ذلك append هي عملية O (1)، والتي ينبغي أن تكون إلا إذا كان المنفذ ميتا في الدماغ. لذلك مع خطوات K كل O (n)، لا يزال لديك عملية O (n).

ما إذا كانت الخطوات التي تم إجراؤها صراحة في التعليمات البرمجية أو ما إذا كانت قد انتهزت تحت أغطية اللغة غير ذات صلة. خلاف ذلك يمكن أن تدعي أن ج qsort كانت عملية واحدة ولديك الآن الكأس المقدسة للروتين (1) الترتيب :-)

كما اكتشف العديد من الناس، يمكنك في كثير من الأحيان التجارة في تعقيد الفضاء لتعقيد الوقت. على سبيل المثال، يعمل ما سبق فقط لأننا يسمح لنا بتقديم isInList و newList المتغيرات. إذا لم يتم السماح بهذا، فقد يقوم الحل الأفضل التالي بفرز القائمة (ربما لا تكون أفضل من O (N تسجيل الدخول N)) متبوعا بعملية O (n) (أعتقد) لإزالة التكرارات.

مثال متطرف، يمكنك استخدام نفس طريقة المساحة الإضافية نفسها لفرز عدد تعسفي من الأعداد الصحيحة 32 بت (قل مع كل منها فقط 255 أو أقل تكرارات) في وقت O (N)، شريطة أن تخصص حوالي أربعة مليارات بايت لتخزين التهم.

ببساطة تهيئة كل التهم إلى الصفر والتشغيل من خلال كل موضع في قائمتك، زيادة العد بناء على الرقم في هذا الموضع. هذا على).

ثم ابدأ في بداية القائمة وتشغيل صفيف العد، مما يضعه العديد من القيمة الصحيحة في القائمة. هذا O (1)، مع وجود 1 حوالي أربعة مليارات بالطبع ولكن لا يزال مستمرا الوقت :-)

هذا أيضا O (1) تعقيد الفضاء ولكن كبير جدا "1". الموازل عادة ليست شديدة.

Answer 2

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

ما لا أفهمه هو ما يسمح للعملية الداخلية مثل set() أن تكون أسرع بكثير من العملية الخارجية لخوارزمية اللغة.لا يزال يتعين إجراء الفحص، أليس كذلك؟

لا يتغير التعقيد المقارب للخوارزمية إذا تم تنفيذها بواسطة منفذي اللغة مقابل تنفيذها بواسطة مستخدم اللغة.وطالما تم تنفيذ كليهما بلغة تورينج الكاملة مع نماذج ذاكرة الوصول العشوائي، فإنهما يتمتعان بنفس القدرات والخوارزميات المطبقة في كل منهما سيكون لها نفس التعقيد المقارب.إذا كانت الخوارزمية من الناحية النظرية O(f(n)) لا يهم إذا تم تنفيذه بلغة التجميع أو C# أو Python، فسيظل كذلك O(f(n)).

Answer 3

تعقد التعقيد مدى الخوارزمية غير مرتبطة تماما بما إذا كان يتم تطبيقه "داخليا" أو "خارجيا"

Answer 4

أخذ قائمة وتحويلها إلى مجموعة من خلال set() هو (ن).

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

لفهم كيف يعمل تنفيذ التجزئة، راجع الفنية ويكيبيديا الجداول التجزئة

Answer 5

خارج اليد لا أستطيع التفكير في كيفية القيام بذلك في O (n)، ولكن هنا هو الشيء الرائع:

الفرق بين n ^ 2 و n هو SOOO ضخمة أن الفرق بينك ينفذه وبيثون ينفذ صغيرا مقارنة بالجوارع المستخدمة لتنفيذها. n ^ 2 هو دائما أسوأ من O (n)، حتى لو كان N ^ 2 في C و O (n) One في Python. يجب ألا تعتقد أن هذا النوع من الفرق يأتي من حقيقة أنك لا تكتب في لغة منخفضة المستوى.

ومع ذلك، إذا كنت ترغب في تنفيذ بنفسك، فيمكنك القيام بالفرز ثم قم بإزالة Dups. النوع هو N * LN (N) وإزالة Dups في O (N) ...

Answer 6

هناك نوعان من القضايا هنا.

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

السرعة الفعلية (قل، في مللي ثانية) من الخوارزمية هي تعقيد الوقت المضروب من قبل ثابت (في عالم مثالي).

يمكن أن يقوم شخصان بتنفيذ نفس إزالة خوارزمية التكرارات مع تعقيد O (سجل (N) * n)، ولكن إذا كتبه المرء في بيثون والآخر يكتبه في ج غير محسن، فسيكون برنامج C أسرع.