Краткое изложение информатики: Алгоритмы, теория и машины Лекция 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".

Сортировка слиянием является рекурсивной процедурой, а также процедурой "разделяй и властвуй". это означает, что если проблема большая, то нужно разбить проблему на подпроблемы, а если проблема становится меньше, то решить ее. и объединить решения маленьких проблем, чтобы получить решение основной проблемы.

Если мы видим вышеприведенные строки, то, наверное, трудно понять, давайте приведем пример ниже.

если мы видим вышеприведенные строки то наверное трудно понять давайте приведем пример

Вот как сделать сортировку слиянием. мы делим {19,98,11,24} на подпроблемы {19,98} , {11,24} и затем {19} {98} {11} {24}, и когда мы разделим этот массив на один элемент, то объединим их (сравним, затем отсортируем & объединим).

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

Ссылки:

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

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

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

Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?

20.08.2023 18:21

Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в 2023-2024 годах? Или это полная лажа?".

Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией

20.08.2023 17:46

В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.

Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox

19.08.2023 18:39

Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в частности, магию поплавков и гибкость flexbox.

Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest

19.08.2023 17:22

В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для чтения благодаря своей простоте. Кроме того, мы всегда хотим проверить самые последние возможности в наших проектах!

Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️

18.08.2023 20:33

Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий их языку и культуре.

Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL

14.08.2023 14:49

Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип предназначен для представления неделимого значения.