Как я объясняю, какова “наивная реализация”? [закрытый]

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

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

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

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

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

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

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

Другой мог бы быть наивной Singleton, которая не составляет поточную обработку.

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

          return obj;
     }
}

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

Пузырьковая сортировка более чем 100 000 тысяч записей.

(Еще не видели действительно наивную реализацию, отправленную так...)

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

   def naive_inverse(x):
        return 1/x

Это будет:

• Повреждение на x=0
• Делает безнадежное дело при передаче целое число

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

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

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

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

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

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

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

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

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

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

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

Попытка Сортировка по неразумному алгоритму !

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

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

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

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 даже, и только потребует приблизительно [1 111] умножение.

Выполнение его самый простой, наименее хитрый доступный путь. Одним примером является вид выбора.

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

Слушающий совет Jon Skeet к основе можно описать вид выбора как:

1. Находят самое высокое значение в списке и помещают, это сначала
2. Находит следующее самое высокое значение и добавляет его к списку
3. Повторный шаг 2, пока у Вас не заканчивается список

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

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

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

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

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

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

• Интуитивно понятное;
• Сначала вписывается;
• часто нефтепользовательны и / или баггические случаи борбана;