عندما كنت أدرس أداء الخوارزميات، صادفت هذا . فهو لا يمنحك فكرة عن كيفية إجراء المقابلات في شركات التكنولوجيا الكبرى فحسب، بل يسمح لك أيضًا بفهم كيفية حل المشكلات الخوارزمية، وبالطريقة الأكثر فعالية الممكنة.
تعتبر هذه المقالة بمثابة مرافقة للفيديو. فيها أقدم تعليقات على جميع الحلول المعروضة، بالإضافة إلى نسختي الخاصة من الحل في JavaScript. كما تمت مناقشة الفروق الدقيقة لكل خوارزمية.
نذكر: لجميع قراء "Habr" - خصم 10 روبل عند التسجيل في أي دورة Skillbox باستخدام رمز "Habr" الترويجي.
يوصي Skillbox بما يلي: دورة عملية .
صياغة المشكلة
لقد تم منحنا مصفوفة مرتبة وقيمة محددة. ثم يُطلب منهم إنشاء دالة ترجع القيمة true أو false اعتمادًا على ما إذا كان مجموع أي رقمين في المصفوفة يمكن أن يساوي قيمة معينة.
بمعنى آخر، هل يوجد عددين صحيحين x و y في المصفوفة، وعند جمعهما معًا يساويان القيمة المحددة؟
مثال أ
إذا تم منحنا مصفوفة [1، 2، 4، 9] والقيمة 8، فسوف تقوم الدالة بإرجاع false لأنه لا يمكن لأي رقمين في المصفوفة أن يصل مجموعهما إلى 8.
المثال ب
ولكن إذا كانت المصفوفة [1, 2, 4, 4] والقيمة هي 8، فيجب أن ترجع الدالة true لأن 4 + 4 = 8.
الحل 1: القوة الغاشمة
تعقيد الوقت: O(N²).
تعقيد الفضاء: O(1).
المعنى الأكثر وضوحا هو استخدام زوج من الحلقات المتداخلة.
const findSum = (arr, val) => {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
if (i !== j && arr[i] + arr[j] === val) {
return true;
};
};
};
return false;
};هذا الحل ليس فعالاً لأنه يتحقق من كل مجموع ممكن لعنصرين في المصفوفة، ويقارن أيضًا كل زوج من المؤشرات مرتين. (على سبيل المثال، عندما i = 1 و j = 2، يكون الأمر في الواقع مماثلاً للمقارنة مع i = 2 و j = 1، ولكن في هذا الحل نحاول كلا الخيارين.)
نظرًا لأن حلنا يستخدم زوجًا من حلقات for المتداخلة، فهو حل تربيعي مع تعقيد زمني O(N²).
الحل 2. البحث الثنائي
تعقيد الوقت: O(Nlog(N)).
تعقيد الفضاء: O(1).
نظرًا لأن المصفوفات مرتبة، فيمكننا البحث عن حل باستخدام البحث الثنائي. هذه هي الخوارزمية الأكثر كفاءة للمصفوفات المرتبة. يحتوي البحث الثنائي نفسه على وقت تشغيل O(log(N)). ومع ذلك، لا يزال يتعين عليك استخدام حلقة for للتحقق من كل عنصر مقابل جميع القيم الأخرى.
وهنا ما قد يبدو عليه الحل. ولتوضيح الأمور، نستخدم وظيفة منفصلة للتحكم في البحث الثنائي. وأيضًا وظيفة removeIndex()، التي تقوم بإرجاع إصدار المصفوفة مطروحًا منه الفهرس المحدد.
const findSum = (arr, val) => {
for (let i = 0; i < arr.length; i++){
if (binarySearch(removeIndex(arr, i), val - arr[i])) {
return true;
}
};
return false;
};
const removeIndex = (arr, i) => {
return arr.slice(0, i).concat(arr.slice(i + 1, arr.length));
};
const binarySearch = (arr, val) => {
let start = 0;
let end = arr.length - 1;
let pivot = Math.floor(arr.length / 2);
while (start < end) {
if (val < arr[pivot]) {
end = pivot - 1;
} else if (val > arr[pivot]) {
start = pivot + 1;
};
pivot = Math.floor((start + end) / 2);
if (arr[pivot] === val) {
return true;
}
};
return false;
};تبدأ الخوارزمية من المؤشر [0]. ثم يقوم بإنشاء نسخة من المصفوفة باستثناء الفهرس الأول ويستخدم البحث الثنائي لمعرفة ما إذا كان من الممكن إضافة أي من القيم المتبقية إلى المصفوفة للحصول على المجموع المطلوب. يتم تنفيذ هذا الإجراء مرة واحدة لكل عنصر في المصفوفة.
ستكون حلقة for نفسها ذات تعقيد زمني خطي يبلغ O(N)، ولكن داخل حلقة for نقوم بإجراء بحث ثنائي، مما يعطي تعقيدًا زمنيًا إجماليًا يبلغ O(Nlog(N)). يعتبر هذا الحل أفضل من الحل السابق، ولكن لا يزال هناك مجال للتحسين.
الحل 3. الزمن الخطي
تعقيد الوقت: O(N).
تعقيد الفضاء: O(1).
الآن سنقوم بحل المشكلة، مع الأخذ بعين الاعتبار أن المصفوفة تم فرزها. الحل هو أن نأخذ رقمين: واحد في البداية وواحد في النهاية. إذا كانت النتيجة تختلف عن المطلوب، فإننا نقوم بتغيير نقطة البداية ونقطة النهاية.
في النهاية سوف نواجه القيمة المطلوبة ونرجع القيمة true، أو سوف تتقارب نقاط البداية والنهاية ونرجع القيمة false.
const findSum = (arr, val) => {
let start = 0;
let end = arr.length - 1;
while (start < end) {
let sum = arr[start] + arr[end];
if (sum > val) {
end -= 1;
} else if (sum < val) {
start += 1;
} else {
return true;
};
};
return false;
};الآن كل شيء على ما يرام، ويبدو أن الحل هو الأمثل. ولكن من يضمن أن المجموعة تم تنظيمها؟
ماذا بعد؟
للوهلة الأولى، قد يبدو من الممكن أن نقوم ببساطة بفرز المصفوفة أولاً ثم استخدام الحل المذكور أعلاه. ولكن كيف سيؤثر هذا على وقت التنفيذ؟
أفضل خوارزمية هي خوارزمية الفرز السريع مع تعقيد زمني O(Nlog(N)). إذا استخدمناه في الحل الأمثل لدينا، فسيتغير أداءه من O(N) إلى O(Nlog(N)). هل من الممكن إيجاد حل خطي مع مصفوفة غير مرتبة؟
الحل 4
تعقيد الوقت: O(N).
تعقيد الفضاء: O(N).
نعم يوجد حل خطي، وهو يتطلب إنشاء مصفوفة جديدة تحتوي على قائمة المطابقات التي نبحث عنها. المقايضة هنا هي استخدام المزيد من الذاكرة: هذا هو الحل الوحيد في الورقة مع تعقيد الفضاء أكبر من O (1).
إذا كانت القيمة الأولى في المصفوفة المحددة هي 1 وقيمة البحث هي 8، فيمكننا إضافة القيمة 7 إلى مصفوفة "قيم البحث".
بعد ذلك، أثناء معالجة كل عنصر من عناصر المصفوفة، يمكننا التحقق من مصفوفة "قيم البحث" ومعرفة ما إذا كان أحدها يساوي قيمتنا. إذا كانت الإجابة بنعم، قم بإرجاع true.
const findSum = (arr, val) => {
let searchValues = [val - arr[0]];
for (let i = 1; i < arr.length; i++) {
let searchVal = val - arr[i];
if (searchValues.includes(arr[i])) {
return true;
} else {
searchValues.push(searchVal);
}
};
return false;
};جوهر الحل هو حلقة for، والتي، كما رأينا أعلاه، لها تعقيد زمني خطي O(N).
الجزء الثاني من التكرار لوظيفتنا هو Array.prototype.include() ، وهي طريقة JavaScript ستعيد القيمة true أو false اعتمادًا على ما إذا كانت المصفوفة تحتوي على القيمة المحددة.
لمعرفة تعقيد الوقت لـ Array.prototype.includes()، يمكننا أن نأخذ بعين الاعتبار polyfill الذي يوفره MDN (والمكتوب في JavaScript)، أو استخدام الطريقة في الكود المصدر لمحرك JavaScript مثل Google V8 (C++).
// https://tc39.github.io/ecma262/#sec-array.prototype.includes
if (!Array.prototype.includes) {
Object.defineProperty(Array.prototype, 'includes', {
value: function(valueToFind, fromIndex) {
if (this == null) {
throw new TypeError('"this" is null or not defined');
}
// 1. Let O be ? ToObject(this value).
var o = Object(this);
// 2. Let len be ? ToLength(? Get(O, "length")).
var len = o.length >>> 0;
// 3. If len is 0, return false.
if (len === 0) {
return false;
}
// 4. Let n be ? ToInteger(fromIndex).
// (If fromIndex is undefined, this step produces the value 0.)
var n = fromIndex | 0;
// 5. If n ≥ 0, then
// a. Let k be n.
// 6. Else n < 0,
// a. Let k be len + n.
// b. If k < 0, let k be 0.
var k = Math.max(n >= 0 ? n : len - Math.abs(n), 0);
function sameValueZero(x, y) {
return x === y || (typeof x === 'number' && typeof y === 'number' && isNaN(x) && isNaN(y));
}
// 7. Repeat, while k < len
while (k < len) {
// a. Let elementK be the result of ? Get(O, ! ToString(k)).
// b. If SameValueZero(valueToFind, elementK) is true, return true.
if (sameValueZero(o[k], valueToFind)) {
return true;
}
// c. Increase k by 1.
k++;
}
// 8. Return false
return false;
}
});
}هنا جزء التكرار من Array.prototype.include() هو حلقة while في الخطوة 7، والتي (تقريبًا) تعبر الطول الكامل للمصفوفة المحددة. وهذا يعني أن تعقيد الوقت خطي أيضًا. حسنًا، نظرًا لأنه يتأخر دائمًا بخطوة واحدة عن مجموعتنا الرئيسية، فإن التعقيد الزمني هو O(N + (N - 1)). باستخدام تدوين Big O، نقوم بتبسيطه إلى O(N) - لأن N هو الذي له التأثير الأكبر مع زيادة حجم الإدخال.
أما بالنسبة لتعقيد الفضاء، فنحن بحاجة إلى مصفوفة إضافية يكون طولها يعكس المصفوفة الأصلية (ناقص واحد، نعم، ولكن يمكن تجاهل ذلك)، مما يؤدي إلى تعقيد فضاء يبلغ O(N). حسنًا، يضمن زيادة استخدام الذاكرة أقصى قدر من كفاءة الخوارزمية.
آمل أن تجد هذه المقالة مفيدة كإضافة لمقابلة الفيديو الخاصة بك. إنه يوضح أن مشكلة بسيطة يمكن حلها بطرق مختلفة مع استخدام كميات مختلفة من الموارد (الوقت والذاكرة).
يوصي Skillbox بما يلي:
- دورة تطبيقية عبر الإنترنت .
- دورة على شبكة الإنترنت .
- دورة سنة عملية .
المصدر: www.habr.com
