Рубрики

Алгоритмы Примеры вопросов | Рецидивы | Набор 2

  • Вопрос 1: Какова сложность T (n)?
    1. 1 ( 1n )
    2. Θ ( 1n 2 )
    3. Θ (1)
    4. Θ (ln (n))

    Ответ: 3
    Пояснение: Используя технику замещения для решения данной рекурсивной функции, замкнутую форму (нерекурсивную форму) T (n) можно индуктивно угадать следующим образом:

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

    Делая это разложение, значения A и B будут найдены как -1 и +1, соответственно. При выполнении этого разложения нерекурсивная форма T (n) записывается как:

    Расширение этого компактного представления T (n) приведет к:

    Как должно быть очевидно, каждая дробь, кроме первой и последней, представлена дважды, но каждый раз с противоположным знаком; Итак, все дроби исчезнут, кроме первой и последней:

    Из последнего уравнения, которое только что было получено, асимптотическая сложность T (n) имеет вид:

  • Вопрос 2: Определите (подсчитайте) общее возможное количество строк длины N с четырьмя символами {a, b, c, d}, содержащими четное число «a» s? [C (N) является сокращением от функции Count (N) для этой цели.]
    1. C (N) = 5,0 * 3, N-1 — 1,0 * 5, N-1.
    2. C (N) = 1,0 * 4 N + 6
    3. C (N) = 0,5 * 2 N + 0,5 * 4 N
    4. C (N) = 1,0 * 2 N + 2,0 * (3) N
    Example: 
    
    For n = 1, there are 3 distinct strings: C(3) = 3
    
    • б, в, д.

    Для n = 2, r, для n = 2, 10 возможных строк: C (10) = 10

    • аа, BB, CC, дд, BC, BD, CB, CD, дБ, DC

    Ответ: 3
    Объяснение: Существует два возможных сценария для первого символа строк с заданным ограничением:

    1. Первый символ может быть одним из возможных символов «b», «c» или «d», кроме «a». В этом случае цель состоит в том, чтобы найти количество строк оставшейся длины «N-1», которые составлены из четного числа «a» s.
      • C (N) = 3 * C (N-1)
    2. Первый символ может быть «а», а один из «а» уже произошел; следовательно, число возможных строк с нечетными числами «a» должно быть подсчитано. Это число нельзя назвать C (N-1), но C (n) все еще может быть достигнуто с помощью C (N-1).
      • C (N) = 4 N-1 — C (N-1), где:
        • 4 N-1 : общее количество возможных строк длины (N-1) с четырьмя символами
        • C (N-1): количество строк длины (N-1), составленное из четного числа «a».

    Поскольку два различных сценария, упомянутые выше, не могут происходить одновременно, общее количество строк является суммой случаев:

    Два начальных условия, такие как приведенные ниже, необходимы для поиска конкретного решения:

    1. Для n = 1 есть 3 различных строки: b, c, d.
    2. Или, для n = 2, 10 возможных строк: aa, bb, cc, dd, bc, bd, cb, cd, db, dc

    Теперь проблему можно сформулировать так:

    Общее возможное количество строк с заданным ограничением:

  • Вопрос 3: Какая из рекуррентных функций не имеет решения полиномиальной формы?

    Ответ: 1
    Пояснение: Решение всех приведенных выше уравнений требуется, чтобы увидеть решение, для которого опция не является полиномиальной. Должно быть видно, что все решения имеют полиномиальную форму, кроме одного, приведенного в первом варианте. Вот анализ вариантов:

    1. Вариант (1) имеет экспоненциальное решение: чтобы найти однородное решение уравнения, представленного в первом варианте, требуются корни его характеристического уравнения:

      Следовательно, решение имеет экспоненциальный вид:

    2. Вариант (2): Уравнение второго варианта может быть легко решено методом замены:

      Замкнутая форма T (n), которая может быть предположительно индуктивной:

      Это говорит о том, что это полиномиальная функция третьей степени (кубический полином):

    3. Вариант (3): В соответствии с основной теоремой , сложность уравнения, предложенного в третьем варианте, имеет ,
    4. Вариант (4): уравнение четвертого варианта лежит в случае 3 основной теоремы ; следовательно, его сложность ,
  • Вопрос 4: какой из них дает наилучшую оценку асимптотической сложности F (n)?
    1. O (n 3 )
    2. Ω (n 2 )
    3. O (n 2 )
    4. Θ (n 2 )

    Ответ: 4
    Объяснение: Есть несколько хитрых фактов, которые необходимо учесть, прежде чем принимать какое-либо решение по следующим вопросам:

    1. [Нахождение как можно более узкой границы] Наилучшая асимптотическая оценка — это когда поведение сложности выражается через expressed-обозначение. Это главным образом основано на средней производительности алгоритмов, так называемом сценарии среднего случая, который требует сложного анализа, который программисты предпочитают использовать другие нотации, такие как O (); Тем не менее, все же это хорошая практика, чтобы попытаться найти максимально узкую границу.
    2. [Обозначения говорят о бесконечности] Математические асимптотические обозначения очерчивают поведение функций сложности в бесконечности, или когда «n» стремится к очень большой величине. Бесконечность — это гипотетическое и абстрактное понятие, которого невозможно достичь в реальной жизни. Для целей расчетов и для представления о поведении функции число, которое следует учитывать, зависит исключительно от проблемы. В этой задаче, похоже, нет ограничений на размер входных данных «n».
    3. [Осведомленность о ловушках тестировщиков] Чтобы избавиться от потенциальных ловушек, предоставленных тестировщиками, достаточно большое значение должно быть присвоено n; в этой задаче малые значения, такие как 100 или 1000, не должны выбираться. Поскольку существует необходимость сравнивать сложность n 3 для n <100, в сравнении с n 2 для n> 100, значения, превышающие 1000, являются приемлемыми, что приводит к n 2 excel n 3 для n = 100. Даже если бы мы собирались пересчитать F (100) в каждое время вызова, для n> 1000 n 2 всегда больше, чем F (100), который имеет порядок n 3 для небольших значений, таких как n = 100. Значение F (100) может быть просто проигнорировано в необходимых вычислениях для n> 1000.
    4. [В реальных приложениях иногда было бы эффективно использовать некоторое ВСПОМОГАТЕЛЬНОЕ ПРОСТРАНСТВО ПАМЯТИ, чтобы набрать некоторую скорость] В этой задаче было бы хорошей идеей использовать вспомогательное пространство памяти to (1) для сохранения результата F ( 100) сразу для будущего использования, без необходимости пересчитывать F (100) при каждом вызове для n> 100. Таким образом, сложность F (100) будет иметь значение O (1), может быть, просто для чтения значения, а сложность F (n) будет иметь значение Θ (n 2 ) для n> 100.

    Сложность F (n) составляет:

  • Вопрос 5: Какой из них определяет соответствующие диапазоны для k и α (альфа), где выполняется следующее асимптотическое выражение?

    1. α ≥ 0 & k ≤ α
    2. α ≥ 0,1 и k ≥ 0
    3. α> 1 & k ∈ R
    4. α> 0 & k ∈ R

    Ответ: 4
    Объяснение: Существует эффективное решение этой проблемы из очень надежного ресурса, шпаргалки из университета MIT . Однако не все, а важная часть описания, приведенного в этом решении, основана на выводах, которые можно найти на этом шпаргалке MIT.

    Цель состоит в том, чтобы найти область, в которой выражение ln k n ∈ O (n α ) истинно. Худшее условие, при котором это выражение может не сохраняться, — это когда левая сторона выражения становится очень большой, пытаясь заставить правую сторону оставаться как можно меньше; другими словами, попытка присвоить экспоненте «k» большое возможное значение, при этом указав очень маленькие значения для экспоненты «Alpha» с другой стороны. Небольшие значения, даже меньше 1, можно присвоить α. Однако на данный момент α приписывается необязательная конкретная константа E, но еще не отрицательное значение; Neither также не установлена переменная E (n), которая является функцией «n», поскольку это будет совершенно новая задача, а не проблема, описанная в этом вопросе.

    Пусть α = | E | (необязательная малая положительная постоянная) и k> 0; цель состоит в том, чтобы увидеть, верно ли выражение ln k n ∈ O (n E ):

    Применение правила Hopital дает:

    То, что она выводится до сих пор, говорит о том, что для логарифмической функции не существует положительного показателя «k», который может превосходить переменную «n» даже с очень маленькими положительными показателями. Конечно, то же самое верно, когда функции логарифма принимают отрицательные показатели и становятся еще меньше. Другими словами:

    Что если показатель степени Альфа принимает отрицательные значения (α = — | E |)? Поскольку отрицательные показатели означают переворачивать дроби, а перебрасывание дробей сопровождается изменением знака неравенства, это дает:

    О-нотация больше не держится. Следовательно, диапазон, в котором сохраняется упомянутое неравенство, равен k ∈ R & α> 0; На математическом языке:

    для k ∈ R & α> 0

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

    Источник:

    1. MIT Асимптотическая шпаргалка
    2. Сборник иранских университетских экзаменов (с небольшим количеством обобщения, модификации, а также перевода)

Рекомендуемые посты:

Алгоритмы Примеры вопросов | Рецидивы | Набор 2

0.00 (0%) 0 votes