В настоящее время я узнаю о времени выполнения Big O Notation и времени амортизации. Я понимаю понятие линейного времени O (n) , означающее, что размер входных данных пропорционально влияет на рост алгоритма. , , и то же самое относится, например,
...Большинство людей со степенью в CS наверняка знают, что Big O означает . Это помогает нам измерить, насколько (не) эффективен алгоритм на самом деле, и если вы знаете в , к какой категории относится проблема, которую вы пытаетесь решить, в
...Иногда я вижу Θ (n) со странным символом with с чем-то посередине, а иногда просто O (n). Это просто лень печатать, потому что никто не знает, как печатать этот символ, или это означает что-то другое?
Что означает «постоянное амортизированное время», когда речь идет о временной сложности алгоритма?
Существуют ли алгоритмы O (1 / n)?
Или что-нибудь еще, что меньше, чем O (1)?
Я спрашиваю больше о том, что это значит для моего кода. Я понимаю концепции математически, мне просто трудно понять, что они означают концептуально. Например, если кто-то должен выполнить операцию O (1) над структурой данных, я понимаю, что количество операций, которые
...Через некоторое время после использования PHP я заметил, что не все PHP встроили функции так быстро, как ожидалось. Рассмотрим две ниже возможные реализации функции, которая определяет, является ли число простым, используя кэшированный массив простых чисел.
//very slow for large $prime_arrayВ чем разница между нотацией Big-O O(n) и нотацией Little-O o(n)?
Я считаю, что есть способ найти k-й по величине элемент в несортированном массиве длины n в O (n). Или, возможно, это «ожидаемый» O (N) или что-то. Как мы можем это сделать?
Вчера у меня был этот вопрос на тесте Алгоритмов, и я не могу найти ответ. Это сводит меня с ума, потому что это стоило около 40 баллов. Я полагаю, что большинство класса не решило это правильно, потому что я не
...Возможно, скоро я буду преподавать «Курс на Java». Хотя, вероятно, можно с уверенностью предположить, что члены аудитории будут знать нотацию Big-O, вероятно, небезопасно предполагать, что они будут знать, каков порядок различных операций в различных реализациях коллекции.
Я мог бы потратить
...Я видел несколько интересных утверждений о SO хэш-картах Java и времени их поиска O(1). Может кто-нибудь объяснить, почему это так? Если эти хеш-карты не сильно отличаются от любых алгоритмов хэширования, на которые я был куплен, всегда должен существовать набор
Видимо ;-) стандартные контейнеры предоставляют некоторую форму гарантий.
Какие гарантии и каковы различия между различными типами контейнеров?
Работая с страницы SGI (около STL ), я придумал это:
Container Types:
================
Container:
Forward Container
Reverse Container
Random Access Container
Sequence
FrontЯ видел, как этот термин «время доступа O (1)» имел обыкновение означать «быстро», но я не понимаю, что это значит. Другой термин, который я вижу в этом же контексте: «O (n) access time». Может ли кто-нибудь объяснить простым способом, что
...Кажется общеизвестным, что хеш-таблицы могут достигать O (1), но это никогда не имело смысла для меня. Может кто-нибудь, пожалуйста, объясните это? Вот две ситуации, которые приходят на ум:
А. Значение int меньше размера хеш-таблицы. Следовательно, значение является его собственным хешем,
...Согласно статье Википедии о связанных списках , вставка в середину связного списка считается O (1). Я думаю, что это будет O (n). Разве вам не нужно было бы найти узел, который мог бы находиться в конце списка?
Разве этот анализ
...Я наткнулся на этот вопрос: Реализуйте очередь, в которой push_rear (), pop_front () и get_min () являются операциями с постоянным временем.
Изначально я думал об использовании структуры данных с минимальной кучей, которая имеет сложность O (1) для get_min (). Но
...Для бинарного типа дерева поиска структур данных я вижу, что нотация Big O обычно обозначается как O (logn). Имея строчную букву «l» в логе, означает ли это логарифмическую базу e (n), как описано натуральным логарифмом? Извините за простой вопрос, но
...Хотелось бы узнать сложность в обозначении Big O классов STL для мультимножества, карты и хеш-карты, когда: