Чтобы найти принятого человека в списке, существует множество способов поиска по списку
//'key' will be the accepted account public static int search(String key, String[] a) { for(int i = 0; i < a.length; i++) // if you write like that below line, you will compare the 'references' // not the value of strings! //if (a[i]==key) return i; //if the 'value' of a[i] is equal to key, it returns 0 if (a[i].compareTo(key) == 0) return i; return -1; }
Представим, что если строковый массив 'a' состоит из {"alice", "bob", "carlos", "carol", "craig",} и ключом является "craig", то нужно выполнить цикл 5 раз. но если существует 10 миллионов человек и человек, которого мы ищем, находится на 10,000,000-ом индексе, то нужно выполнить цикл 10 миллионов раз, и это займет много времени! поэтому мы должны найти более эффективный способ найти ключ.
Чтобы использовать бинарный поиск, необходимо хранить массив в отсортированном порядке
public class Binary_Search { public static int search(String key, String[] a) { return search(key, a, 0, a.length); } public static int search(String key, String[] a, int lo, int hi) { if (hi <= lo) return -1; int mid = lo + (hi - lo) / 2; int cmp = a[mid].compareTo(key); //compareTo : 1 means : // a[mid] is greater than key,search the half with upper indices if (cmp > 0) return search(key, a, lo, mid); //compareTo : -1 means : // a[mid] is smaller than key,search the half with lower indices // mid + 1 means that you will also remove the 'mid' and search // the mid+1 with lower indicies. else if (cmp < 0) return search(key, a, mid+1, hi); //if cmp == 0,return mid else return mid; } public static void main(String[] args) { String key = "dave"; String[] a = new String[]{"alice","bob","carlos","carol","craig","dave"}; //not 0 like the first index of an array, we have to add 1. int lo = 1; int hi = 6; //find the array where "dave" is in System.out.println(search(key,a,lo,hi)); } }
(* я написал cmp == 0 return mid и a[mid] == key, а не cmp = 0 return mid и a[mid = key])
Таким образом, если мы используем бинарный поиск, мы можем выполнить цикл только 2 раза, в отличие от последовательного поиска, при котором мы должны выполнить цикл 6 раз, чтобы найти Дэйва. Таким образом, мы можем также обнаружить, что временная сложность бинарного поиска будет O(log N).
Но, как я уже говорил, чтобы использовать двоичный поиск, мы должны отсортировать массив до этого. тогда как мы можем отсортировать массив? один из ответов - "сортировка вставкой".
Допустим, если изменить порядок массива, то он будет выглядеть следующим образом
{"craig", "dave", "alice", "bob", "carol", "carlos"}
Но если мы используем сортировку вставкой, мы можем отсортировать массив, чтобы иметь возможность использовать бинарный поиск!
public class Insertion_Sort { public static void sort(String[] a) { int N = a.length; //sort process for(int i = 1; i < N; i++) for(int j = i; j > 0; j--) if (a[j-1].compareTo(a[j])>0) exch(a, j-1, j); else break; } // exchange a[i] and a[j] private static void exch(String[] a, int i, int j) { String t = a[i]; a[i] = a[j]; a[j] = t; } public static void main(String[] args) { String[] a = new String[]{"craig","dave","alice","bob","carol","carlos"}; sort(a); // print the elements for (int i = 0; i < a.length; i++) StdOut.println(a[i]); } }
Я описываю ход сортировки вставкой, остальные циклы вы можете попробовать сами :)
Но временная сложность сортировки вставками составляет O(N) для лучшего, и O(N²) для среднего и худшего, так что если вы попробуете это, вы можете обнаружить, что это должно зацикливаться много раз.
Существует закон Мура, который означает, что "количество транзисторов в интегральной схеме удваивается примерно каждые 2 года". Но если мы используем квадратичный алгоритм, это "удвоение" не означает, что компьютер работает в два раза быстрее.
Джон фон Нейман нашел более эффективный алгоритм сортировки под названием "Merge Sort".
Сортировка слиянием является рекурсивной процедурой, а также процедурой "разделяй и властвуй". это означает, что если проблема большая, то нужно разбить проблему на подпроблемы, а если проблема становится меньше, то решить ее. и объединить решения маленьких проблем, чтобы получить решение основной проблемы.
Если мы видим вышеприведенные строки, то, наверное, трудно понять, давайте приведем пример ниже.
Поэтому мы можем применить сортировку слиянием к {"craig", "dave", "alice", "bob", "carol", "carlos"}, что мы ищем.
public class Merge_Sort { public static void main(String[] args) { //alice : 1, bob = 2, carlos = 3, carol = 4, craig = 5, dave = 6 int numbers[] = { 5, 6, 1, 2, 4, 3}; System.out.println("Before:"); printArray(numbers); mergeSort(numbers); System.out.println("\nAfter:"); printArray(numbers); } private static void mergeSort(int[] inputArray) { int inputLength = inputArray.length; //if there is only one element in divided array, then return. if (inputLength < 2) { return; } //we will 'divide' the inputLength int midIndex = inputLength / 2; int[] leftHalf = new int[midIndex]; int[] rightHalf = new int[inputLength - midIndex]; //copy the elements from our original input array into leftHalf array for(int i = 0; i < midIndex; i++) { leftHalf[i] = inputArray[i]; } //copy the elements from our original input array into rightHalf array for(int i = midIndex; i < inputLength; i++) { //we should fill the rightHalf from the 0th index! rightHalf[i - midIndex] = inputArray[i]; } //recursively divide till return! mergeSort(leftHalf); mergeSort(rightHalf); merge(inputArray, leftHalf, rightHalf); } //int[] inputArray : later we can merge it sorted with leftHalf and rightHalf // private static void merge(int[] inputArray, int[] leftHalf, int[] rightHalf){ int leftSize = leftHalf.length; int rightSize = rightHalf.length; //keep comparing the lowest element of each array //i will be the iterator for the leftHalf //j will be the iterator for the rightHalf //k will be the iterator for the inputArray int i = 0, j = 0 ,k = 0; //looping until we run out of elements in the left array or we run out of elements on the right array while(i < leftSize && j < rightSize) { //compare the ith element of the leftHalf and the jth element of the rightHalf if (leftHalf[i] <= rightHalf[j]) { //if leftHalf[i] is equal or smaller than rightHalf[j], put leftHalf[i] element into inputArray[k] index inputArray[k] = leftHalf[i]; //move the leftHalf array's pointer and then compare incremented leftHalf[i] to rightHalf[j] i++; } else { inputArray[k] = rightHalf[j]; j++; } // move the inputArray's pointer not to duplicate. k++; } // put the elements that remain of the array to the inputArray[k] //if the array is leftHalf while(i < leftSize) { inputArray[k] = leftHalf[i]; i++; k++; } //if the array is rightHalf while(j < rightSize) { inputArray[k] = rightHalf[j]; j++; k++; } } private static void printArray(int[] numbers) { for (int i = 0; i < numbers.length; i++) { System.out.println(numbers[i]); } } }
Временная сложность сортировки слиянием составляет O(n log n), что более эффективно, чем сортировка вставкой, временная сложность которой составляет O(n) для лучшего случая и O(n²) для среднего и худшего.
Я очень хотел написать о LCP(Longest common prefix) и LRS(Longest repeated substring), но думаю, что мне нужно больше практиковаться, потому что я не могу понять это четко из-за недостатка знаний. но я надеюсь, что этот конспект поможет вам!
Ссылки:
Открыть Github GistComputer Science: Алгоритмы, теория и машины
Разделяй и властвуй с помощью MergeSort
https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html
05.05.2023 14:00
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
05.05.2023 11:59
Привет, читатели, сегодня мы узнаем о коллекциях. В Laravel коллекции - это способ манипулировать массивами и играть с массивами данных. Благодаря своим методам, они делают код очень простым для понимания и читабельным.
05.05.2023 11:57
Если вы ищете платформу, которая предоставляет вам бесплатный тест JavaScript MCQ (Multiple Choice Questions With Answers) для оценки ваших знаний, то, не теряя времени, практикуйте наш бесплатный онлайн тест 1100+ JavaScript MCQs и развивайте свои навыки и знания.
05.05.2023 09:26