2-ой по минимальности элемент (порядковая характеристика)

[BanmaN]

Здравствуйте.
В книге Кормен "Алгоритмы построение и анализ" написано, что 2-ой по минималности элемент в массиве можно найти используя $n+[lg n]-2$ сравнений. Подскажите, пожалуйста, алгоритм.

Спасибо.

[sup]

Разбейте все элементы на пары. В каждой паре найдите минимум. Второй по минимальности элемент либо среди этих минимумов, либо в паре с минимальным. Поэтому для каждого минимального в паре запоминаем его "напарника". Далее с "минимальными" поступаем точно так же: разбиваем на пары, находим минимальный, запоминаем напарника и т.д. После последнего сравнения останется единственный элемент - минимальный во всем массиве. Осталось просмотреть всех "напарников" этого элемента. Для хранения напарников, похоже, лучше всего подходят односвязные списки.

[rendall]

А может быть считать промежуточный минимум? Через два вложенных цикла например.

[sup]

rendall
Честно сказать, не понял Вашу мысль. Ограничение на количество сравнений очень жесткое. Для того чтобы просто найти наименьший в массиве нужно $n-1$ сравнений. После этого остается логарифмическое количество сравнений. Разумеется, мы не обязаны искать наименьший элемент, тем не менее данная оценка наводит на размышления.

[Pavia]

Цитата:

Ограничение на количество сравнений очень жесткое.

Не такие они и жесткие. В книге написано, что это наихудший случай.

Цитата:

Разумеется, мы не обязаны искать наименьший элемент, тем не менее данная оценка наводит на размышления.

В книжке есть подсказка - "заодно найти минимальный".

[sup]

Ограничение и в самом деле жесткое. Вот всего лишь пара вопросов.
1. Как доказать что алгоритма с "лучшей" оценкой худшего случая не существует? Ну, или предъявить такой алгоритм.
2. Можно ли предъявить алгоритм с "лучшей" оценкой "в среднем"? Этот вопрос, наверное, наиболее интересен для практической реализации.
А то, что написано в книжке - вполне естественно. Не можем же мы расчитывать на то, что нам "повезет".

[BanmaN]

О! Спасибо за ответ)

sup, в вашем решении ещё используется, получается, дополнительная память. В книге про её вообще ничего не говорилось, но в решении получается, что нужно доп. памяти где-то $ n \cdot lgn - 2n$ (а то и $n \cdot lgn$, конечно, в процессе решения можно будет много чего удалять, но ничего в общем-то это не изменит). (вообще можно и меньше памяти затратить, вроде, но придётся уже выделенныю ранее использовать)

Да, интересно было бы и узнать про решение с меньшим выделением доп. памяти... А то как-то уж совсем неободряюще: ради меньше чем $n$ операций жертвуем таким количеством памяти...

Но спасибо) Алгоритм хороший!

[sup]

Ну $n \log_2 n$ памяти - это уж слишком, хватит и $\sim n$ (я уже упоминал списки). Но вообще, задача имеет, скорее всего, отвлеченное значение. Вся эта возня с дополнительной памятью и запоминанием напарников. Потом второй проход ... Проще в один проход, поддерживая текущие 2 наименьших элемента. Лень считать, но не удивлюсь, если этот алгоритм не уступает предыдущему в среднем.

[BanmaN]

Ну да, это я напутал, конечно, хватит и n. А вот с проходами я не понял, что вы имели ввиду.

[Circiter]

(Приглючило...)

2BanmaN

Цитата:

А вот с проходами я не понял

Участник sup, очевидно, назвал "проходами" стадии последовательной (рекурсивной) обработки "минимальных" элементов пар. Про однопроходный вариант я тоже не понял. :)

Будете смеяться, но когда я прочитал стартовое сообщение, я истолковал условие слишком дословно и написал такой псевдокод:

int SecondMinimal(int *Array, int Length)
{
    int Minimal=0, Result=0;

    for(Index=0; Index<Length; Index++)
        if(Array[Index]<Array[Minimal])
        {
            Result=Minimal;
            Minimal=Index;
        }

    return Result;
}

Причем, истинное значение фразы "второй по минимальности" до меня так и не дошло... :)

[sup]

Я, наверное, "криво" выразился. Очевидное решение таково

int SecondMinimal(int *Array, int Length)
{
    int minIdx=0;
    int secondMinIdx=1;
    if(Array[1]<Array[0])
    {
      minIdx=1;
      secondMinIdx=0;
    }


    for(int Index=2; Index<Length; Index++)
    {
        if(Array[Index]<Array[secondMinIdx])
        {
           if(Array[Index]<Array[minIdx])
           {
              secondMinIdx=minIdx;
              minIdx=Index;
           }
           else
              secondMinIdx=Index;
        }
    }
    return secondMinIdx;
}

Можно показать, что в среднем требуется порядка $n +2\ln n$ сравнений (если нет одинаковых элементов, т.е. все элементы различные).
Что до "двухпроходной схемы", то я имел в виду следующее: первый проход - поиск абсолютного минимума с запоминанием напарников и т.д. (возможно рекурсивно), а второй проход - просмотр напарников для поиска второго по минимальности элемента.