Блог

Главная - Вопросы по программированию - Сравнить три значения в NlogN

Сравнить три значения в NlogN

#algorithm

#алгоритм

Вопрос:

Как можно взять массив и сравнить три значения в массиве, не сравнивая значения более одного раза.

Я могу выполнить итерацию с тремя вложенными циклами, но это приведет к тому, что один и тот же внутренний блок будет вызываться три раза. Мне нужно время NlogN.

 For Loop
    For Loop
        For Loop
            add values and store if greater than max

Комментарии:

1. Глядя на строку «добавить значения и сохранить, если больше max», я задаюсь вопросом — почему бы просто не отсортировать массив и не добавить 3 наибольших значения?

2. Можете ли вы немного уточнить, чего вы пытаетесь достичь здесь? Сравнение трех значений массива? Друг с другом? Какие три значения? Что вы хотите получить в результате операции?

3. что значит «сравнить 3 значения»? вы ищете наибольшую сумму из 3 чисел? просто найдите 3 самых больших, это O (n)

4. Я просто добавил это для простоты. Я думаю, я не должен был. На самом деле происходит вызов функции, где порядок значений не имеет значения. check_for_validity(A,B, C)

5. @Matt: Совместимо!? Что это значит ?!

Ответ №1:

Я не уверен, что я правильно понял вопрос, но вы можете захотеть сделать что-то вроде этого:

 for i from 1 to N {
    for j from i 1 to N {
        for k from j 1 to N {
            if (i j k > currentMax) {
                // do stuff
            }
        }
    }
}

Комментарии:

1. Я понятия не имею, является ли это тем, чего он пытается достичь, но это определенно не удовлетворяет ограничению сложности

2. @amit: его ограничение сложности не имело для меня никакого смысла, поэтому я сосредоточился на аспекте отсутствия избыточности при сравнении каждой тройки значений.

3. @PengOne; Похоже, ваш алгоритм O(n^3) .

4. @ypercube Да. Смотрите мой комментарий выше.