адрес проектаGitHub.com/push АО Вэй/.…
Хотя бы раз в неделю спрашивайте о проблемах и оскорблениях
Простая структура
├──Package
│ ├── Sort 排序篇
│ │ ├── BubbleSort.php 冒泡排序
│ │ ├── HeapSort.php 堆排序 大根堆
│ │ ├── MBaseSort.php 基数排序 MSD
│ │ ├── LBaseSort.php 基数排序 LSD
│ │ ├── QuickSort.php 快速排序
│ │ ├── ShellSort.php 希尔排序
│ │ ├── MergeSort.php 归并排序
│ │ ├── InsertSort.php 插入排序
│ │ └── SelectSort.php 选择排序
│ │
│ ├── Query 查找篇
│ │ ├── BinaryQuery.php 二分查找
│ │ ├── InseertQuery.php 插入查找
│ │ ├── FibonacciQuery.php 斐波那契查找
│ │ └── QulickQuery.php 快速查找
│ │
│ ├── Structure 数据结构
│ │ ├── StackExample.php 堆栈 先进后出 LIFO (Last In First Out)
│ │ ├── LinearChain.php 线性表 单链存储
│ │ └── LinearOrder.php 线性表 顺序存储
│ │
│ ├── Tools 小工具集
│ │ └── SystemSwitch.php 堆栈实现进制转换
│ │
│ └── Other 其他
│ ├── MonkeyKing.php 约瑟夫环
│ ├── DynamicProgramming.php 动态规划
│ ├── Fibonacci.php 斐波那契数列
│ ├── StealingApples.php 偷苹果求余
│ ├── HanoiGames.php 汉诺塔游戏
│ ├── BidirectionalQueue.php 双向队列
│ ├── ColorBricks.php 彩色砖块
│ ├── GetCattle.php 牛年求牛
│ ├── OnlyNumbers.php 求唯一数
│ ├── PokerGames.php 洗扑克牌
│ └── BigSmallReplace.php Hello World 输出 Olleh Dlrow
│
├──LICENSE
└──README.md
Что делать?
记录自己理解算法，数据结构的过程，尽可能的简单全面以及详细，让算法学习运用灵活自如，加油(ง •̀_•́)ง
Конечно
用 PHP 实现算法并替代官方提供的函数是愚蠢的事情 .但这觉不代表斟酌算法就是件无意义的事 , 每个算法都是一种思想的结晶 , 学习优秀的思想 , 开拓思维
Что такое алгоритм?
Проще говоря, алгоритм — это любой четко определенный вычислительный процесс, который принимает в качестве входных данных некоторое значение или набор и выдает некоторое значение или набор в качестве выходных данных. Таким образом, алгоритм представляет собой серию вычислительных процессов, которые преобразуют входные данные в выходные. Источник: Томас Х. Кормен, Чейлз Э. Лейзерсон (2009 г.), Введение в алгоритмы, 3-е издание.
В двух словах можно сказать, что алгоритм — это последовательность шагов, используемых для решения конкретной задачи (да, не только компьютеры используют алгоритмы, но и люди). В настоящее время эффективный алгоритм должен содержать три важных свойства:
- Он должен быть конечным: алгоритм, который вы разрабатываете, бесполезен, если он бесконечно пытается решить проблему.
- Он должен иметь четко определенные инструкции: каждый шаг алгоритма должен быть точно определен, и инструкции в любом случае должны быть однозначными.
- Он должен быть эффективным: алгоритм разработан для решения проблемы, затем он должен быть в состоянии решить проблему, и можно показать, что алгоритм сходится, используя только бумагу и ручку.
логарифм
log10100 эквивалентно вопросу "сколько 10 умножить и результат будет 100", ответ конечно 2
так журнал10100=2, то есть операция логарифмирования является обратной операцией операции возведения в степень
| left | right |
|---|---|
| 23 = 8 | log28 = 3 |
| 24 = 16 | log216 = 4 |
| 25 = 32 | log232 = 5 |
Драться! несовершеннолетний
часы работы
Возьмем в качестве примера бинарный поиск. Сколько времени можно сэкономить, используя его? Простой поиск Чжугэ Ди проверяет номер, если в списке 100 номеров, требуется до 100 догадок.
Другими словами, максимальное количество догадок совпадает с длиной списка, которое называется линейным временем, а бинарный поиск отличается, если список содержит 100 элементов.
Требуется до 7 догадок, если список содержит 4 миллиарда чисел, требуется до 32 догадок, а подпоиск выполняется за логарифмическое время.O(log)
Обозначение большого O
Обозначение Big O — это специальное обозначение, указывающее, насколько быстр алгоритм. Прикольная штука в использовании, ведь часто приходится копировать чужой код. В этом случае узнайте, насколько быстры или медленны эти алгоритмы.
-
Время работы алгоритма увеличивается с разной скоростью.
- Например, разница между простым поиском и бинарным поиском
| элемент | простой поиск | бинарный поиск |
|---|---|---|
| 100 элементов | 100ms | 7ms |
| 10000 элементов | 10s | 14ms |
| 1 000 000 000 элементов | 11 дней | 30ms |
- Большой
OУказывает, насколько быстр алгоритм, например, список содержитnэлементы, простой поиск должен проверять каждый элемент, поэтому вам нужно сделатьnоперации
использовать большиеOУказывает, что это время работыO(n), бинарный поиск должен выполнять журналnопераций, использовать большиеOВыражается какO(log n)
-
Некоторые распространенные среды выполнения big-O
- O(log n) , также известное как логарифмическое время, такие алгоритмы включают алгоритм деления пополам
- O(n), также называемое линейным временем, такие алгоритмы включают простые поиски.
- O(n * log n) быстрая сортировка
- O(n2), сортировка выбором
- O(n!) или факториальное время
-
вот в чем дело
- Скорость алгоритма зависит не от времени, а от скорости операндов.
- Когда мы говорим о скорости алгоритма, мы имеем в виду, насколько быстро будет увеличиваться время его работы по мере увеличения входных данных.
- Время работы алгоритма выражается в большой нотации O.
- O (log n) быстрее, чем O (n), когда нужно искать больше элементов, первое намного быстрее, чем последнее.
Процесс написания программ, решающих реальные проблемы
- Как описать проблему в форме данных, то есть абстрагировать проблему в математическую модель
- Количество данных, вовлеченных в проблему, и взаимосвязь между данными
- Как хранить данные в компьютере и отражать взаимосвязь между данными
- Что делать с данными при их обработке
- Хорошая ли производительность написанной программы
Данные
- Это символическое представление объективных вещей.В информатике это общий термин для всех символов, которые могут быть введены в компьютер и обработаны компьютерной программой.
- Элемент данных (Data Element): это базовая единица данных, которая обычно рассматривается и обрабатывается в программе как единое целое. Элемент данных может состоять из нескольких элементов данных (элемент данных).
- Элемент данных (Data Item): это наименьшая неделимая единица данных. Элемент данных — это описание данных определенного аспекта объективной вещи.
- Объект данных: это набор элементов данных одинаковой природы и подмножество данных. Например, набор символов C={'A','B','C,…}.
- Структура данных: набор элементов данных, связанных друг с другом.
- Логическая структура данных: взаимосвязь между элементами данных называется логической структурой.
- Операции с данными: операции, выполняемые над данными
- Тип данных: относится к набору значений и общему термину для набора операций, определенных для набора значений.
Существует четыре основных типа логической структуры данных.
- Коллекция: нет никакой другой связи между элементами данных в структуре, кроме «принадлежности к одной и той же коллекции».
- Линейная структура: между элементами данных в структуре существует отношение один к одному.
- Древовидная структура: элементы данных в структуре имеют отношение «один ко многим».
- Структура сети или графа: между элементами данных в структуре существует отношение «многие ко многим».
Как хранятся структуры данных
В соответствии с отношениями между элементами данных в компьютере существует два разных метода представления - последовательное представление и непоследовательное представление, из которых выводятся два метода хранения, последовательная структура хранения и цепная структура хранения.
- Последовательная структура хранения: логическая структура (отношение) между элементами данных представлена относительным положением элементов данных в памяти, а адреса элементов данных непрерывны.
- Связанная структура хранения: добавьте указатель (указатель) для хранения адреса другого элемента в каждом элементе данных и используйте этот указатель для представления логической структуры (отношения) между элементами данных. элементы данных непрерывны.
Логическая структура и физическая структура данных являются двумя неразделимыми аспектами.Разработка алгоритма зависит от выбранной логической структуры, а реализация алгоритма зависит от используемой структуры хранения.
Алгоритм
представляет собой описание метода (этапа) решения конкретной задачи и представляет собой конечную последовательность инструкций, где каждая инструкция представляет собой одну или несколько операций.
Алгоритм имеет следующие пять свойств
- Конечность: алгоритм всегда должен заканчиваться после выполнения конечных шагов, каждый из которых выполняется за конечное время.
- Детерминированный: каждая инструкция в алгоритме должна иметь точное значение, двусмысленность отсутствует, алгоритм имеет только один вход и один выход.
- Выполнимость: Алгоритм выполним, то есть операции, описанные алгоритмом, могут быть реализованы путем выполнения ограниченного числа основных операций, которые были реализованы.
- Входные данные: алгоритм имеет ноль или более входных данных, которые берутся из определенного набора объектов.
- Выход: Алгоритм имеет один или несколько выходов, которые представляют собой величины, имеющие определенное отношение к входным данным.
Алгоритмы и программы - это два разных понятия
Компьютерная программа — это конкретная реализация алгоритма с использованием языка программирования. Тот факт, что алгоритм должен быть завершен, означает, что не все компьютерные программы являются алгоритмами.
Есть несколько критериев оценки хорошего алгоритма:
- Корректность: Алгоритм должен соответствовать потребностям конкретной задачи.
- Удобочитаемость: Алгоритмы должны быть просты для чтения и общения людьми.Алгоритмы с хорошей удобочитаемостью полезны для понимания и модификации алгоритмов.
- Надежность: алгоритм должен иметь отказоустойчивую обработку, когда вводятся недопустимые или неправильные данные, алгоритм должен иметь возможность реагировать или обрабатываться соответствующим образом, не создавая необъяснимых выходных результатов.
- Общность: Алгоритм должен иметь общность, то есть результаты обработки алгоритма действительны для общих наборов данных.
Требования к эффективности и хранилищу: эффективность относится ко времени выполнения алгоритма, требования к хранилищу относятся к максимальному объему памяти, необходимому во время выполнения алгоритма, как правило, эти два параметра связаны с масштабом проблемы.
Временная сложность алгоритма
Количество повторений основных операций в алгоритме является функцией размера задачи n, а его измерение времени обозначается как T(n)=O(f(n)), что называется асимптотической временной сложностью алгоритма (Асимптотическая временная сложность), временная сложность для краткости
Пространственная сложность алгоритма
Это относится к измерению пространства для хранения, необходимого, когда алгоритм записывается в программу и запускается на компьютере, обозначается как: S (n) = O (f (n)), где n - размер проблемы.
Простое сравнение рекурсии и цикла:
- С программной точки зрения рекурсия проявляется как вызов самой себя, а цикл такой формы не имеет.
- Рекурсия начинается с конечной цели задачи, и постепенно превращает сложные задачи в простые, а решение простых задач такое же, как и сложных задач, при этом есть исходная ситуация, и задачу можно решить. наконец получено, что является обратным. Цикл начинается с простой проблемы, развивается шаг за шагом и, наконец, находит проблему, которая положительна.
- Любой цикл может быть представлен рекурсией, но если вы хотите использовать цикл для реализации рекурсии (за исключением однонаправленной рекурсии и хвостовой рекурсии), вы должны ввести структуру стека, чтобы помещать и извлекать стек.
- В общем случае нерекурсивный метод более эффективен, чем рекурсивный. А рекурсивные вызовы функций имеют накладные расходы, а количество рекурсий ограничено размером стека.
учиться вместе
- Разветвите мой проект и отправьте свой
idea - Pull Request
- Merge
исправление ошибки
Если вы обнаружите, что что-то не так, вы можете инициироватьissueилиpull request, со временем исправлю
Дополнение: пожалуйста, обратитесь к статье для сообщения о коммите, которое инициирует запрос на вытягивание.Сообщение фиксации и руководство по написанию журнала изменений
Спасибо
Спасибо следующим друзьям за проблему или запрос на включение:
License
MIT