Краткое изложение информатики: Алгоритмы, теория и машины Лекция 11-1 (Сортировка и поиск)

RedDeveloper
04.01.2023 18:22
Краткое изложение информатики: Алгоритмы, теория и машины Лекция 11-1 (Сортировка и поиск)
  • Черный список - это список прав доступа, которые должны быть отклонены для обслуживания.
  • Белый список - это список прав, которые должны быть приняты на обслуживание.
  • Итак, что мы хотим сделать, это составить белый список более эффективно!

Чтобы найти принятого человека в списке, существует множество способов поиска по списку

1. Мы можем использовать последовательный поиск с помощью цикла for

//'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 миллионов раз, и это займет много времени! поэтому мы должны найти более эффективный способ найти ключ.

2. Бинарный поиск

Чтобы использовать бинарный поиск, необходимо хранить массив в отсортированном порядке

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).

Но, как я уже говорил, чтобы использовать двоичный поиск, мы должны отсортировать массив до этого. тогда как мы можем отсортировать массив? один из ответов - "сортировка вставкой".

3. Сортировка вставкой

Допустим, если изменить порядок массива, то он будет выглядеть следующим образом

{"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 года". Но если мы используем квадратичный алгоритм, это "удвоение" не означает, что компьютер работает в два раза быстрее.

4. Сортировка слиянием

Джон фон Нейман нашел более эффективный алгоритм сортировки под названием "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]);
        }
    }
}
поэтому мы можем применить сортировку слиянием к {"craig" "dave" "alice" "bob"

Временная сложность сортировки слиянием составляет O(n log n), что более эффективно, чем сортировка вставкой, временная сложность которой составляет O(n) для лучшего случая и O(n²) для среднего и худшего.

Временная сложность сортировки слиянием составляет O(n log n) что более эффективно чем

Я очень хотел написать о LCP(Longest common prefix) и LRS(Longest repeated substring), но думаю, что мне нужно больше практиковаться, потому что я не могу понять это четко из-за недостатка знаний. но я надеюсь, что этот конспект поможет вам!

Ссылки:

Открыть Github Gist

Computer Science: Алгоритмы, теория и машины

Разделяй и властвуй с помощью MergeSort

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

Почему в Python есть оператор &quot;pass&quot;?
Почему в Python есть оператор "pass"?

05.05.2023 14:00

Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.

Коллекции в Laravel более простым способом
Коллекции в Laravel более простым способом

05.05.2023 11:59

Привет, читатели, сегодня мы узнаем о коллекциях. В Laravel коллекции - это способ манипулировать массивами и играть с массивами данных. Благодаря своим методам, они делают код очень простым для понимания и читабельным.

JavaScript Вопросы с множественным выбором и ответы
JavaScript Вопросы с множественным выбором и ответы

05.05.2023 11:57

Если вы ищете платформу, которая предоставляет вам бесплатный тест JavaScript MCQ (Multiple Choice Questions With Answers) для оценки ваших знаний, то, не теряя времени, практикуйте наш бесплатный онлайн тест 1100+ JavaScript MCQs и развивайте свои навыки и знания.

Массив зависимостей в React
Массив зависимостей в React

05.05.2023 09:44

Все о массиве Dependency и его связи с useEffect.