Member 11512486 Ответов: 3

Как рассчитать временную сложность шаг за шагом данной двухпрограммной программы


Программа-1:

for (i = 0; i < m, i + +){
    for (j = 0; j < n, j + +){
      if (a = b){
        arr[i][j] = 1;
      }
      else{
        arr[i][j] = 2;
      }
    }
}

for (i = 0; i < m, i + +){
    for (j = 0; j < n, j + +){
      arr[i] += arr[i][j];
    }
}

for (i = 0; i < m, i + +){
  if (a = b){
    p[i] = i
    q [i] = i
  }
}


Программа-2:

for (i = 0; i < m, i + +){
  sum = 0;
    for (j = 0; j < n, j + +){
      if (a = b){
        arr[i][j] = 1
        sum += 1;
      }
      else{
         arr[i][j] = 2
      }
    }
    if (c = d){
      arr[i] = sum;
      p[i] = i
      q [i] = i
    }   
}


Что я уже пробовал:

Я попытался шаг за шагом составить уравнение временной сложности для обеих программ. а какой из них лучше и на сколько? Не могли бы вы помочь мне с этим?

для программы-1:
м*н*С1 + М*Н*С2 + м*С3

для программы-2
m*n*c1 + m*c2

3 Ответов

Рейтинг:
2

Patrice T

Не ваш вопрос, но ваши программы ошибочны:

if (a = b){ // this store value of b in a

должен быть заменен на:
if (a == b){ // this compare a and b for equality


Рейтинг:
2

OriginalGriff

Как вы думаете, что быстрее? Посмотрите на сложности, которые вы вычислили, и сравните их.
O(1) имеет фиксированное время: независимо от того, сколько выборок данных используется, он всегда будет выполняться в одно и то же время.
O(N) напрямую сравнивает количество выборок данных со временем выполнения линейным способом: если вы увеличите N с 10 до 20, время выполнения удвоится.
O(2N) также линейно, если вы увеличите N с 10 до 20, время выполнения также удвоится. Сложность эквивалентна, но медленнее, чем O(2N)
O(N2) экспоненциально - небольшое увеличение N приводит к большому увеличению времени выполнения.

Посмотрите на ваши две сложности, и это довольно очевидно, что быстрее, если вы подумаете об этом.

Это ваше домашнее задание, а не наше: ваш учитель ищет ваши мысли, а не мои. Так что попробуйте!


Рейтинг:
2

CPallini

Временная сложность обеих программ составляет O(m x n)- так зачем же беспокоиться?