Какова временная сложность этого peudo code? - PullRequest
Новая
       112

Какова временная сложность этого peudo code?

0 голосов
/ 21 июня 2020

Я не очень разбираюсь в вычислениях сложности. Можете ли вы помочь оценить сложность следующих псевдокодов?

Алгоритм 1: 

Input: V1, V2 and V3 and another vector C// Vectors of size n
Output: response..
V_f = f(V1, V2, 3) // function performs simple multiplication and additions on the vector
for i in range(0,n) // loop over element in the vector
     if V_f(i) != C(i) 
              // sort the V1(i), V2(i) and V3(i) and retrieve the middle value
              // if the middle value is in a range of certain values then launch Algorithm 2  
             // Over the result of Algorithm 2 (using if expressions), print the response
// end and return result

Алгоритм 2 

Input: Sorted

 Values C{1}, C{2} and C{3} and the vector C

Output: Response:

for i in range (o,n) // loop over the elements 
       // According to the values of C and C{i}, perform additions (using if expressions)
// end and return result

Операции внутри циклов являются просто сложениями или простые тесты. Кроме того, алгоритм 2 выполняется с помощью алгоритма 1, что означает, что у меня есть al oop внутри al oop (верно?): 

for i in range (n)
// operations
// for j in range (n)
// operations

Значит ли это, что временная сложность этого алгоритма составляет O(n^2) ? где n - размер вектора?

Также в качестве общего вопроса, если алгоритм 1 и алгоритм 2 выполняются параллельно, какова общая сложность? это сумма или максимум сложности каждого алгоритма?

1 Ответ

1 голос
/ 21 июня 2020

Алгоритм1

  1. Алгоритм1 сначала выполнит простое умножение и сложение векторов. Предполагая, что он проходит цикл от начала до конца для каждого вектора и выполняет некоторые вычисления, количество сделанных итераций будет 3*N , что будет считаться O(N)

    V_f = f(V1, V2, 3)          #Time complexity will be O(N)

  2. Следующее оператор в первом алгоритме также будет l oop из 0 to N. Предполагая, что в каждом случае V_f(i) != C(i), вам нужно будет отсортировать V1[i], V2[i], V3[i], что займет постоянное O(1) время. 

    for i in range(0,n) // loop over element in the vector
    if V_f(i) != C(i)

    В следующем операторе вы проверка - среднее значение перечисленных выше отсортированных элементов находится в определенном диапазоне - // if the middle value is in a range of certain values then launch Algorithm 2 , теперь временная сложность этого зависит от того, как выполняется проверка и насколько велик диапазон. Я предполагаю, что вам нужно проверять в непрерывном диапазоне от a до b, поэтому этот шаг займет только O(1). Теперь будет вызван алгоритм 2.

алгоритм 2

Алгоритм 2 - 

 for i in range (o,n) // loop over the elements 
        // According to the values of C and C{i}, perform additions (using if expressions)
 // end and return result

Здесь вы снова будете зацикливаться с 0 to N и выполнять некоторые вычисления на каждой итерации, что займет O(1). Таким образом, общая временная сложность будет O(N) для всего алгоритма2.

Значит ли это, что временная сложность этого алгоритма составляет O (n ^ 2)?

Теперь, в худшем случае, вам придется запускать алгоритм 2 в каждом итерация внутри l oop алгоритма algorthm1. Итак, временная сложность будет O(N^2), как вы сказали. Обратите внимание, что это также будет зависеть от того, насколько просты вычисления, как выполняется проверка в диапазоне определенных значений, и будет способствовать константе в нашей окончательной временной сложности. Но если предположить, что они не превышают O(N), общая временная сложность будет O(N^2)

...