ما هو س الوقت في تحديد ما إذا كانت قيمة هو في مرتبة المصفوفة ؟

Question

لدي مجموعة مرتبة من 5000 الاعداد الصحيحه.سريع كيف يمكنني معرفة ما إذا كان عشوائي صحيح هو عضو في مجموعة ؟ الجواب في العام ، ج روبي سيكون من الرائع.

مجموعة القيم من شكل

c * c + 1

حيث c يمكن أن يكون أي عدد صحيح من 1 إلى 5000.

على سبيل المثال:

[2, 5, 10, 17, 26, 37, 50 ...]

Answer 1

وبحث ثنائي، كما ذكر آخرون، هو O (log2N)، ويمكن أن تكون مشفرة إما بشكل متكرر:

   BinarySearch(A[0..N-1], value, low, high) {
       if (high < low)
           return -1 // not found
       mid = (low + high) / 2
       if (A[mid] > value)
           return BinarySearch(A, value, low, mid-1)
       else if (A[mid] < value)
           return BinarySearch(A, value, mid+1, high)
       else
           return mid // found
   }

وأو تكرارا:

   BinarySearch(A[0..N-1], value) {
       low = 0
       high = N - 1
       while (low <= high) {
           mid = (low + high) / 2
           if (A[mid] > value)
               high = mid - 1
           else if (A[mid] < value)
               low = mid + 1
           else
               return mid // found
       }
       return -1 // not found
   }

ولكن، إذا كنت تبحث عن أسرع طريقة ممكنة، يمكنك إنشاء جدول البحث على أساس sqrt(N-1) من الأرقام الخاصة بك. مع فقط 5000 كلمات من الذاكرة يمكنك تحقيق O (1) عمليات البحث بهذه الطريقة.

شرح:

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

مثال:

إليك نموذج التعليمات البرمجية في بيثون، الذي يقرأ مثل شبة الكود، كما هو الحال دائما: -)

import math

N = 5000
ar = [17, 26, 37, 50, 10001, 40001]

lookup_table = [0] * N

for val in ar:
    idx = int(math.sqrt(val - 1))
    lookup_table[idx] = 1

def val_exists(val):
    return lookup_table[int(math.sqrt(val - 1))] == 1

print val_exists(37)
print val_exists(65)
print val_exists(40001)
print val_exists(90001)

وبناء الجدول يستغرق فترة تصل O (N) على الأكثر، وعمليات البحث وO (1).

Answer 2

وسجل (ن) للبحث ثنائي على ج

Answer 3

وأود أن أقول انها O (CONST)! :)

ونظرا رقم عشوائي ص، انها تافهة للتحقق سواء كان ذلك في العدد الذي يمكن أن تكون ممثلة في شكل (ن * ن + 1). فقط تأكد ما إذا كان الجذر التربيعي (ص-1) هو عدد صحيح أم لا!

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

Answer 4

ومن الناحية الفنية، ومدى تعقيد إيجاد عنصر في مجموعة ذات حجم ثابت ثابت، منذ سجل <الفرعية> 2 5000 لن تتغير.

Answer 5

وثنائي البحث هو O (سجل ن)

يكيبيديا

Answer 6

O (سجل ن) إذا كان لديه مجموعة عناصر ن

Answer 7

فقط للتوسع في ذلك:انها lg n الاختبارات التي يتم سجل₂ ن.أن يجعل O(سجل ن).لماذا ؟ لأن كل محاكمة البحث الثنائي يقسم مجموعة في النصف ؛ وبالتالي فإنه يأخذ lg ن المحاكمات.

Answer 8

واستخدام البحث الثنائي، انها دخول (N) وقت البحث.

bool ContainsBinarySearch(int[] array, int value) {
  return Array.BinarySearch(arrray, value) >= 0;
}

Answer 9

في بيرل:

وأود أن تحميل القيم في تجزئة ثابتة، ومن ثم سوف يكون O (1).

تحليل بناء تجزئة بحث

وlookup_hash {$ _} = 1 foreach (original_array)؛

تحليل تركيب بحث

و($ lookup_hash {$ lookup_value}) && الطباعة "وجدت أنه في O (1) - لا حلقة هنا \ ن"؛