Рубрики

Алгоритмы Примеры вопросов | Набор 3 | Анализ временного порядка

Вопрос 1: Что такое асимптотическая граница T (n)?

  1. θ (n * log (n))
  2. θ (n 2 )
  3. θ (н)
  4. θ (n * log 2 (n))
  5. θ (n 2 * log 2 (n))

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

Что касается указания этих границ, есть несколько советов, как следующие:

  • Это очевидно, что для любого k, большего √ n , каждый log k n должен быть меньше log √n n = 2, а больше log n n = 1. На математическом языке:
    1. Подсказка на ВЕРХНЕЙ границе, для k> √ n :

    2. Подсказка на НИЖНЕЙ границе, для k> √ n :

  • Кроме того, с увеличением основания логарифма его значение уменьшается; таким образом, ни один из членов, полученных в результате раскрытия первой сигмы, не может быть больше первого тер, log 2 n, и не может быть меньше последнего, который является log n n; в других предложениях,
    1. Еще один намек на верхнюю границу, но на этот раз для k <√ n :

    2. Еще один намек на НИЖНЮЮ границу, но на этот раз для k <√ n :

После этих подсказок дает:

  1. Нижняя граница:

  2. Верхняя граница:

То, что было получено до сих пор, указывает на то, что рост T (n) не может превышать O (n) и не может быть меньше Ω (n); Следовательно, асимптотический порядок сложности T (n):

Вопрос 2: Каков порядок времени выполнения данной программы?

C PROGRAM: Input n of type integer
  for(i= 2; i<n; i=i+1)
   for(j = 1; j < n; j= j * i)
    // A line of code of Θ(1)
  1. θ (н)
  2. θ (n * log (n))
  3. θ (n 2 )
  4. θ (n * log 2 log (n))
  5. θ (n 2 * log 2 (n))

Ответ: 1

Пояснение: Время выполнения каждой строки указано ниже отдельно:

  1. Первая строка кода, t 1 (n), имеет вид:
    for (i = 2; i <n; i = i + 1) // выполняется (n — 2) раза; поэтому временная сложность этой линии составляет θ (n)
  2. Вторая строка кода, t 2 (n):
    для (j = 1; j <n; j = j * i) // log 2 n + log 3 n +… + log n-1 n = Σlog i n ∈ Θ (n) в соответствии с ПРЕДЫДУЩИМ ВОПРОСОМ этой статьи (См. Вопрос 1)
  3. Третья строка кода, t 3 (n):
    // Строка кода из Θ (1) :: Inside циклов, поэтому время ее заказа такое же, как и в предыдущей строке, которая имеет Θ (n)

Общая временная сложность T (n) программы является суммой каждой строки t i (n), i = 1..3, следующим образом:

Вопрос 3: Дается следующее рекуррентное уравнение T (n). Сколько предложенных функций g i (n), i = 1 .. 5, приемлемо для того, чтобы T (n) ∈ θ (f (n)), когда f (n) = g i (n)?



  1. 1
  2. 2
  3. 3
  4. 4
  5. 5

Ответ: 2
Пояснение: Основная теорема и ее расширение могут помочь в решении этой проблемы. Общая форма основной теоремы может быть выражена как:

Чтобы использовать основную теорему , необходимо убедиться, что данная задача с конкретными «a», «b» и «f (n)» удовлетворяет условию того, какой случай этой теоремы. Три случая основной теоремы и их условия:

  • Случай 1: Этот случай случается, что дерево рекурсии слишком сложное (работа по разделению / рекомбинации проблемы затмевается подзадачами.)

  • Случай 2: Этот случай возникает, когда работа по разделению / рекомбинации проблемы сопоставима с подзадачами.


  • Случай 3: Этот случай имеет место, когда дерево рекурсии тяжело задано корнем (работа по разделению / рекомбинации проблемы доминирует над подзадачами.)

Обобщенный второй случай основной теоремы, так называемая расширенная основная теорема , обрабатывает все значения k. Это говорит:

Ответ на этот вопрос — третий случай основной теоремы, где T (n) имеет значение Θ (f (n)); таким образом, чтобы T (n) = θ (f (n)), между n log b a и f (n) должна быть полиномиальная разность «эпсилон»; следовательно, функции g 1 (n) и g 2 (n) удовлетворяют условиям третьего случая основной теоремы. Найденное для них значение «эпсилон» составляет 1 и 0,01 соответственно.

Вопрос 4: Какая опция описывает истинный асимптотический анализ для этой программы с множественными входными переменными, в то же время имея представление (предварительное знание) об относительном росте входных данных, например, m ∈ ∈ (n)?

 C PROGRAM: inputs m and n of type integer 
  for(i= 1; i<= n; i=i+1) : n
   for(j = 1; j <= m; j= j * 2)
    for(k = 1; k <= j; k= k+1)
     \\ A code line of Θ(1)
  1. θ (n * m * (m + 1) / 2)
  2. θ (n * m + n * log 2 (m))
  3. θ (м 3 )
  4. θ (n 2 )
  5. θ (n 2 * log 2 (n))

Ответ: 4

Пояснение: Чтобы вычислить временную сложность программы на основе входных данных n и m, T (n, m), первым шагом является получение времени выполнения каждой строки, t i (n, m), как указано ниже:

  1. for (i = 1; i <= n; i = i + 1) // выполняется n раз

  2. for (j = 1; j <= m; j = j * 2) // повторяет log 2 (m) раза и находится внутри другого цикла, который умножает его n раз

  3. for (k = 1; k <= j; k = k + 1) // выполняется 2 + 4 + 8 +… + 2 log (m) раз

    Это также внутри внешнего цикла, первого цикла for, который сам повторяется n раз

  4. // Строка кода Θ (1) То же, что и предыдущая строка, Θ (m * n)

Общий порядок выполнения этой программы:

Это может быть даже более упрощено в соответствии с данными предшествующими знаниями, которые говорят, что m ∈ Θ (n) или n ∈ Θ (m):

Вопрос 5: Существует вектор целых чисел, называемый V [], который имеет длину «N».
Для конкретной задачи (программы) задано, что Σ i = 1 N | V [i] | = P.
Какова временная сложность следующего фрагмента кода? [Излишне говорить, что P также является целым числом]

Tmp = -1;
  For r= 1 to N
   For S = 1 to V[r]
    Tmp = Tmp + 20;
  1. O (N + 2 * N * P)
  2. НА СТР )
  3. O (N 2 )
  4. O (P 2 )
  5. O (2 * P + N)

Ответ: 5
Объяснение: Количество времени выполнения каждой строки и их общая сложность по времени указаны ниже:

Tmp = -1; // θ (1)
Для r = 1 до N // N раз; так что это θ (N)
Для S = 1 до V [r] // Не может быть больше, чем | V [r] | раз; поэтому общее количество раз составляет O (Σr = 1 N | V [r] |) = O (P)
Tmp = Tmp + 20; // То же, что и в предыдущей строке, O (P)

Чтобы определить временную сложность данной программы, необходимо учитывать три факта:

  1. Каждый V [r] может принимать любое целочисленное значение (даже нулевое или отрицательное), но это не имеет значения, поскольку все отрицательные значения не приведут к выполнению второго цикла в таких языках программирования, как C. Однако в языках программирования это разрешено считать до (или перебирать) отрицательные числа, но алгоритмы, которые не анализируются, зависят от языков программирования, а анализ основан только на самом алгоритме. Что точно сказать, это информация, которая дается в вопросе; поэтому хитрое действие заключается в рассмотрении абсолютного значения | V [r] | а также использовать нотацию O () , чтобы избавиться от застревания. В противном случае нужно сказать, что программа выполняется как минимум столько же времени, сколько требуется для простого выполнения первого цикла, или Ω (N)
  2. Хотя порядок времени выполнения этой программы, кажется, не зависит от двух переменных, но больше нет информации для дальнейшего анализа, который необходим для сравнения P и N; таким образом, асимптотическая сложность зависит от значений как P, так и N; другими словами, вместо T (N) существует функция сложности T (N, P).
  3. Нотация O () определяет более свободную границу, чем жесткая граница, указанная в нотации & theta (); Следовательно, сумма θ () и O () будет иметь тип O (). В этой задаче общая временная сложность программы, которая представляет собой сумму всех сложностей строк кода, θ (1) + θ (N) + O (P) + O (P) , принадлежит множеству O (2 * P). + N + 1) или O (2 * P + N).

С учетом всех факторов, упомянутых выше, одна асимптотическая сложность может иметь T (N, P) ∈ O (2 * | P | + N); Однако коэффициенты переменных не важны на последнем этапе асимптотического анализа, поскольку все они принадлежат одному и тому же набору функций сложности, и сложность также может быть выражена как O (| P | + N).

Источник:

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

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

Алгоритмы Примеры вопросов | Набор 3 | Анализ временного порядка

0.00 (0%) 0 votes