Как объяснить, что такое "наивная реализация"?

Ответ 1

Я бы попытался полностью отключить его от компьютеров. Спросите свою аудиторию, как они находят запись в словаре. (Нормальный словарь определения слов.)

Наивная реализация должна начинаться с самого начала и смотреть на первое слово. О, это не то слово, которое мы ищем - посмотрим на следующий и т.д. Стоит отметить, что они, вероятно, даже не думали об этом, - мы достаточно умны, чтобы снижать его немедленно! Это, однако, про самый простой способ, о котором вы могли подумать. (Возможно, было бы интересно спросить их, могут ли они придумать что-нибудь более простое и проверить, действительно ли они понимают, почему это проще, чем то, как мы это делаем.)

Следующая реализация (и довольно хорошая) - это начало в середине словаря. Подходит ли слово, которое мы ищем, до или после этого? Если это раньше, перейдите на страницу на полпути между началом и тем, где мы сейчас находимся - в противном случае перейдите на страницу наполовину между тем, где мы находимся сейчас, а конец и т.д. - бинарная отбивная.

Фактическая реализация человека заключается в том, чтобы использовать наше знание писем, чтобы очень быстро добраться до "почти правильного места" - если мы увидим "слона", тогда мы узнаем, что это будет "где-то рядом с началом", может быть, около 1/5-й путь. Как только мы добрались до E (что мы можем сделать с очень, очень простыми сравнениями), мы найдем EL и т.д.

Ответ 2

StackOverflow Jeff Atwood имел отличный пример наивного алгоритма, связанного с перетасовкой массива.

Ответ 3

Сделать это самым простым, наименее сложным способом. Одним из примеров является сортировка выбора.

В этом случае наивность не означает плохой или непригодный для использования. Это просто не очень хорошо.

Взяв совет Джона Скита, вы можете описать сортировку как:

• Найти наивысшее значение в списке и поместить его первым
• Найдите следующее самое высокое значение и добавьте его в список
• Повторите шаг 2, пока не закончите список.

Это легко сделать и легко понять, но не обязательно лучше.

Ответ 4

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

Ответ 5

Какой самый очевидный, наивный алгоритм для возведения в степень, о котором вы могли подумать?

base ** exp base * base * ... * base, exp раз:

double pow(double base, int exp) {
    double result = 1;
    for (int i = 0; i < exp; i++)
        result *= base;
    return result;
}

Он не обрабатывает отрицательные показатели. Помня, что base ** exp == 1 / base ** (-exp) == (1 / base) ** (-exp):

double pow(double base, int exp) {
    double result = 1;
    if (exp < 0) {
        base = 1 / base;
        exp = -exp;
    }
    for (int i = 0; i < exp; i++)
        result *= base;
    return result;
}

Фактически можно вычислить base ** exp с точностью менее чем exp, хотя!

double pow(double base, int exp) {
    double result = 1;
    if (exp < 0) {
        base = 1 / base;
        exp = -exp;
    }
    while (exp) {
        if (exp % 2) {
            result *= base;
            exp--;
        }
        else {
            base *= base;
            exp /= 2;
        }
    }
    return result * base;
}

Это использует тот факт, что base ** exp == (base * base) ** (exp / 2), если exp четный, и потребуется только умножение log2(exp).

Ответ 6

Я нашел время, чтобы прочитать ваш вопрос немного ближе, и у меня есть прекрасный пример.

хороший пример, который иллюстрирует - в идеале даже для нетехнических людей - что наивная реализация может технически быть функциональным решением проблемы, но практически полностью непригодна для использования.

Попробуйте Bogosort!

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

Ответ 7

"Наивная реализация" почти всегда является синонимом "реализации грубой силы". Наивные реализации часто интуитивно понятны и первыми приходят на ум, но также часто O (n ^ 2) или хуже, поэтому слишком много слишком практично для больших входов.

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

Ответ 8

Определить, является ли число простым или нет (тест на соответствие) - отличный пример.

Наивный метод просто проверяет, является ли n mod x, где x = 2..square root (n) равно нулю, по крайней мере, для одного x. Этот метод может быть очень медленным для очень больших простых чисел, и это нецелесообразно использовать в криптографии.

С другой стороны, существует пара вероятностей или быстрых детерминированных тестов. Они слишком сложны для объяснения здесь, но вы можете проверить соответствующую статью в Википедии по этому вопросу для получения дополнительной информации: http://en.wikipedia.org/wiki/Primality_test

Ответ 9

Скажем, кто-то выясняет, как извлечь одно поле из базы данных, а затем переходит к написанию веб-страницы в PHP или на любом языке, который делает отдельный запрос в базе данных для каждого поля на странице. Он работает, но будет невероятно медленным, неэффективным и сложным в обслуживании.

Ответ 10

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

Классическим примером, конечно, является сортировка. В контексте сортировки списка из десяти чисел любой старый алгоритм (кроме pogo sort) будет работать очень хорошо. Однако, когда мы доходим до масштабов тысяч чисел или более, мы обычно говорим, что выбор сортировки является наивным алгоритмом, поскольку он имеет качество O (n ^ 2) времени, которое было бы слишком медленным для наших целей, и что не наивный алгоритм - это quicksort, потому что он имеет качество O (n lg n), которое достаточно быстро для наших целей.

Фактически, можно сделать вывод, что в контексте сортировки списка из десяти чисел quicksort является наивным алгоритмом, так как он займет больше времени, чем выбор.

Ответ 11

Наивная реализация:

• интуитивное;
• сначала нужно иметь в виду;
• часто неэффективные и/или багги-инктерные случаи;

Ответ 12

Bubble сортирует более 100 000 тыс. записей.

Ответ 13

Интуитивно понятные алгоритмы, которые вы обычно используете для сортировки колоды карт (insertion sort или сортировка сортировки, как O (n ^ 2)), можно считать наивными, потому что их легко освоить и реализовать, но не будет хорошо масштабироваться до колоды, скажем, 100000 карт: D, В общем случае существуют более быстрые (O (n log n)) способы сортировки списка.

Обратите внимание, однако, что наивное не обязательно означает плохое. Бывают ситуации, когда сортировка вставки - хороший выбор (скажем, когда у вас уже отсортированная большая колода и несколько несортированных карт для добавления).

Ответ 14

(Не видел поистине наивной реализации, но так...)

Следующая реализация является "наивной", потому что она не охватывает случаи краев и будет ломаться в других случаях. Это очень просто понять и передать сообщение программирования.

   def naive_inverse(x):
        return 1/x

Он будет:

• Перерыв на x = 0
• Выполнять неудачную работу при передаче целого числа

Вы можете сделать его более "зрелым", добавив эти функции.

Ответ 15

A O (n!) алгоритм.

foreach(object o in set1)
{
    foreach(object p in set1)
    {
        // codez
    }
}

Это будет выполняться отлично с небольшими наборами, а затем экспоненциально хуже с более крупными.

Другим может быть наивный Синглтон, который не учитывает потоки.

public static SomeObject Instance
{
     get
     {
          if(obj == null)
          {
               obj = new SomeObject();
          }

          return obj;
     }
}

Если два потока обращаются к ним, в то же время они могут получить две разные версии. Приводят к серьезным странным ошибкам.