В предыдущей статье Insight from Harvard Cs50 (1) я кратко коснулся концепций, рассмотренных в лекции 3 об алгоритмах, чтобы позже объяснить больше здесь! Давайте погрузимся прямо в!
Следующие примечания дополнены соответствующими временными метками видео:
Если вы нашли определенный элемент в списке:
00:13:02 — линейный поиск(O(n): линейная временная сложность)
function linearSearch(arr, target) { for (let i = 0; i < arr.length; i++) { if (arr[i] === target) { return i; // Return the index where the target is found } } return -1; // Return -1 if target is not found } const arr = [3, 7, 2, 8, 5]; const target = 8; const index = linearSearch(arr, target); if (index !== -1) { console.log(`Target ${target} found at index ${index}`); } else { console.log(`Target ${target} not found in the array`); }
00:22:57 — Двоичный поиск (O(log n): логарифмическая временная сложность)
Если число отсортировано с предположением,используются условные операторы (if-else) и рекурсия вместо использования традиционного цикла (линейный поиск).
//iterative version of the binary search algorithm using a loop function binarySearch(arr, x) { let low = 0; let high = arr.length - 1; while (low <= high) { let mid = Math.floor((low + high) / 2); if (arr[mid] === x) { return true; // Element found } else if (arr[mid] < x) { low = mid + 1; // Search the right half } else { high = mid - 1; // Search the left half } } return false; // Element not found }
так что такое рекурсия?
Представьте, как ваша мама избивает вас, ребята (извините, память азиатских детей 90-х): сначала старший брат, затем младший, затем вы и, наконец, ваша младшая сестра. В то время как и циклы, и рекурсия повторяют действия, рекурсия разбивает вещи от большего к меньшему, следуя определенным правилам (в отличие от поиска через двери).
Рекурсия позволяет избежать использования явных циклов, в то время как двоичный поиск может быть реализован с использованием либо рекурсии, либо циклов сопределенными правилами для сужения поиска.
function binarySearchRecursive(arr, target, low, high) { if (low > high) { return -1; // Base case: target not found } let mid = Math.floor((low + high) / 2); if (arr[mid] === target) { return mid; // Base case: target found at index mid } else if (arr[mid] < target) { return binarySearchRecursive(arr, target, mid + 1, high); // Search right half } else { return binarySearchRecursive(arr, target, low, mid - 1); // Search left half } } const arr = [2, 4, 6, 8, 10, 12, 14, 16]; const target = 10; const index = binarySearchRecursive(arr, target, 0, arr.length - 1); if (index !== -1) { console.log(`Target ${target} found at index ${index}`); } else { console.log(`Target ${target} not found in the array`); }
рекурсия будет позже обсуждаться, давайте двигаться дальше.
00:51:21 — структуры
Используется для обозначения пользовательского типа данных с несколькими полями, вы можете провести сравнение с тем, как интерфейсы TypeScript работают в JavaScript.
//a struct in C struct Student { int id; char name[50]; float gpa; }; //in TS interface Student { id: number; name: string; gpa: number; }
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Если вы хотите отсортировать список элементов:
Два неудачных способа:
01:14:41 — Сортировка выбором (O(n²))
function selectionSort(arr) { const n = arr.length; //check all for (let i = 0; i < n - 1; i++) { let minIndex = i; //get the next compare number from the loop i itself for (let j = i + 1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } if (minIndex !== i) { // Swap elements const temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } return arr; } const unsortedArray = [64, 34, 25, 12, 22, 11, 90]; const sortedArray = selectionSort(unsortedArray); console.log("Unsorted array:", unsortedArray); console.log("Sorted array:", sortedArray);
01:36:22 — пузырьковая сортировка (O(n²))
function bubbleSort(arr) { const n = arr.length; for (let i = 0; i < n - 1; i++) { // Last i elements are already in place, no need to compare them for (let j = 0; j < n - i - 1; j++) { // Compare adjacent elements and swap if necessary if (arr[j] > arr[j + 1]) { const temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } return arr; } const unsortedArray = [64, 34, 25, 12, 22, 11, 90]; const sortedArray = bubbleSort(unsortedArray); console.log("Unsorted array:", unsortedArray); console.log("Sorted array:", sortedArray);
Реализация использования рекурсии более эффективна, чем описанная выше.
01:54:32 — Рекурсия (разделяй и властвуй)
- Разделить: несортированный список делится на две половины.
- Завоевание: каждая половина рекурсивно сортируется с использованием одного и того же алгоритма.
- Объединить: отсортированные части объединяются вместе, чтобы получить окончательный отсортированный список.
02:04:22 — Сортировка слиянием (O(n log n))
Большой бинарный поиск = алгоритмы «разделяй и властвуй» (слияние, быстрота, алгоритм Штрассена)
function mergeSort(arr) { if (arr.length <= 1) { return arr; // Base case: already sorted or single element } const middle = Math.floor(arr.length / 2); const leftHalf = arr.slice(0, middle); const rightHalf = arr.slice(middle); return merge(mergeSort(leftHalf), mergeSort(rightHalf)); } function merge(left, right) { let result = []; let leftIndex = 0; let rightIndex = 0; while (leftIndex < left.length && rightIndex < right.length) { if (left[leftIndex] < right[rightIndex]) { result.push(left[leftIndex]); leftIndex++; } else { result.push(right[rightIndex]); rightIndex++; } } return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex)); } const unsortedArray = [64, 34, 25, 12, 22, 11, 90]; const sortedArray = mergeSort(unsortedArray); console.log("Unsorted array:", unsortedArray); console.log("Sorted array:", sortedArray);