Поиск максимумов и минимумовУсложним задачу. Пусть нам требуется найти минимальный элемент в неупорядоченном массиве. Оказывается, что и эта задача имеет линейную сложность, и для поиска минимального (максимального) элемента в неупорядоченном массиве требуется n – 1 сравнение. Запишем алгоритм поиска максимального элемента в текстовой форме. Алгоритм поиска максимального элемента в неупорядоченном массиве: 1. Установить счетчик равным 1 (i = 1). 2. Положим значение текущего максимума равным первому исследуемому элементу (max = a1). 3. Если исследованы еще не все элементы (i < n), то перейти к шагу 5, иначе алгоритм окончен (максимальный элемент равен max). 4. Перейти к следующему элементу (увеличить i на единицу). 5. Если рассматриваемый элемент больше, чем текущий максимум (ai > max), то значение ai присвоить max. 6. Перейти к шагу 4. Приведем блок-схему аналогичного алгоритма поиска минимального элемента: Скачать текст программы Можно еще усложнить задачу и найти одновременно максимальный и минимальный элементы. Скорректируем вышеприведенный алгоритм. Алгоритм одновременного поиска максимального и минимального элементов в неупорядоченном массиве: 1. Установить счетчик равным 1 (i = 1). 2. Положим значения текущего минимума и текущего максимума равными первому исследуемому элементу (min = a1, max = a1). 3. Если исследованы еще не все элементы i < n), то перейти к шагу 4, иначе алгоритм окончен (минимальный и максимальный элементы равны min и max соответственно). 4. Перейти к следующему элементу (увеличить i на единицу). 5. Если текущий элемент меньше чем минимум (ai < min), то присвоить min значение ai, иначе если текущий элемент больше, чем максимум (ai > max), то присвоить max значение ai 6. Перейти к шагу 3. Запишем этот алгоритм в виде блок-схемы: Скачать текст программы Сложность этого алгоритма равна 2 · (n – 1). Возникает вопрос, существует ли алгоритм одновременного поиска минимального и максимального элемента, сложность которого меньше, чем 2 · (n – 1)? Оказывается, такой алгоритм существует, и его сложность равна 3 · (n/2). Эффективный алгоритм поиска максимального элемента в неупорядоченном массиве:
1. Разбить массив на пары (получим n/2 пар, при нечетном n плюс еще одна неполная пара). 2. Упорядочить по возрастанию каждую пару (при выполнении этого шага будет выполнено (n/2) сравнений). Тогда в массиве на всех нечетных местах будут стоять минимальные для каждой пары числа, а на всех четных местах – максимальные. 3. Найти минимальное число, осуществляя поиск только среди элементов, стоящих на нечетных местах. При этом если у нас есть неполная пара, то в качестве начального значения переменной min взять значение элемента неполной пары (при выполнении этого шага будет выполнено (n/2) сравнений). 4. Найти максимальное число, осуществляя поиск только среди элементов, стоящих на четных местах. При этом если у нас есть неполная пара, то в качестве начального значения переменной max взять значение элемента неполной пары (при выполнении этого шага будет выполнено (n/2) сравнений). Всего сравнений в этом алгоритме 3 · (n/2). Скачать текст программы
|
