У меня есть алгоритм, который открывает текстовый файл, читает от 5 до 20 слов, сохраняет их в массив и снова закрывает текстовый файл.Big O Notation для чтения текстового файла с 5-20 словами
Имеет ли этот алгоритм Big O Natation (1) или (n)?
Я собираюсь пойти против общего мнения здесь и сказать, что это O(n), где n - средняя длина слова. Ясно, что если длина этих 20 слов удваивается, то и объем работы, который вам нужно сделать, чтобы прочитать их.
Если максимальная длина слов также постоянна, это будет O(1).
Я с вами на этом. Простое чтение и отбрасывание их - это «O (n)». – Blrfl
Это также O (n), где n - размер входных данных (в файле), и это более традиционное определение 'n', чем что-либо, связанное с в среднем. Не то, чтобы в этом случае это имело какое-либо значение, где, конечно, размер данных ограничен ниже на 5 * в среднем и выше на 20 * в среднем, поэтому эти два эквивалентны в любом случае. –
слова «реальный»,/«общие» слова, например, продукты или места или месяц. длина слов не больше чем (я думаю) 20 букв (если я получу вас правильно) в моем специальном случае – Tyzak
O (1) он всегда будет использовать ограниченное количество операций.
Это O (1), если вы не сообщите нам, что должно быть n.
. Я думал, например, поисковым алгоритмом, чтобы пройти через массив, имеет O (n) [насколько это возможно Я выучил]. n будет переменной. (потому что число не исправить, но число ограничено 5-20 словами] – Tyzak
В этом случае 'n' - это, вероятно, количество элементов в массиве. Оно не упоминается явно, но довольно очевидно. В вашем случае , это не так очевидно, что должно быть 'n'. Размер файла? Число слов, которое должен прочитать алгоритм? Или (как предположил sepp2k) средняя длина слова? – Oswald
Если каждый раз, когда выполняется алгоритм, он считывает не более 20 слов, то это O (1), так как время, затрачиваемое на выполнение алгоритма, не увеличивается, поскольку количество слов в текстовый файл увеличивается.
Как выбраны эти 5-20 слов? – Gumbo
они выбраны более или менее администратором, поэтому они не будут увеличиваться и не будут превышать лимит – Tyzak