2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

Спасибо.

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

 
 
 
 Re: 2-ой по минимальности элемент (порядковая характеристика)
Сообщение23.06.2011, 07:42 
Аватара пользователя
А может быть считать промежуточный минимум? Через два вложенных цикла например.

 
 
 
 Re: 2-ой по минимальности элемент (порядковая характеристика)
Сообщение23.06.2011, 08:19 
rendall
Честно сказать, не понял Вашу мысль. Ограничение на количество сравнений очень жесткое. Для того чтобы просто найти наименьший в массиве нужно $n-1$ сравнений. После этого остается логарифмическое количество сравнений. Разумеется, мы не обязаны искать наименьший элемент, тем не менее данная оценка наводит на размышления.

 
 
 
 Re: 2-ой по минимальности элемент (порядковая характеристика)
Сообщение23.06.2011, 09:04 
Аватара пользователя
Цитата:
Ограничение на количество сравнений очень жесткое.

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

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

 
 
 
 Re: 2-ой по минимальности элемент (порядковая характеристика)
Сообщение23.06.2011, 20:53 
О! Спасибо за ответ)

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

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

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

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

 
 
 
 Re: 2-ой по минимальности элемент (порядковая характеристика)
Сообщение24.06.2011, 09:13 
Ну да, это я напутал, конечно, хватит и n. А вот с проходами я не понял, что вы имели ввиду.

 
 
 
 Re: 2-ой по минимальности элемент (порядковая характеристика)
Сообщение25.06.2011, 03:19 

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

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;
}

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

 
 
 
 Re: 2-ой по минимальности элемент (порядковая характеристика)
Сообщение25.06.2011, 17:21 
Я, наверное, "криво" выразился. Очевидное решение таково
Код:
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$ сравнений (если нет одинаковых элементов, т.е. все элементы различные).
Что до "двухпроходной схемы", то я имел в виду следующее: первый проход - поиск абсолютного минимума с запоминанием напарников и т.д. (возможно рекурсивно), а второй проход - просмотр напарников для поиска второго по минимальности элемента.

 
 
 [ Сообщений: 11 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group