Расчет сложности времени. Нужна помощь в достижении конечного результата - PullRequest
Новая
       2

Расчет сложности времени. Нужна помощь в достижении конечного результата

0 голосов
/ 08 февраля 2012

Завтра учусь в среднесрочной перспективе, и с этими сложностями во времени я борюсь.Я перебираю простые примеры в книге и для этого примера

Сортировка Exchange 

void exchangesort (int n, keytype S[])
{
  index i, j;
  for(i=1; i<=n-1; i++)
    for(j=i+1; j<=n; j++)
      if(S[j] < S[i])
        exchange S[i] and S[j];
}

Для "временной сложности каждого случая" этого ExchangeСортировка, я понимаю ту часть, которую мы в значительной степени анализируем для цикла j, потому что он имеет базовую операцию (обмен).И поэтому, если вы укажете общее количество проходов, оно будет дано следующим образом: 

T(n) = (n-1) + (n-2) + (n-3) + ... + 1 = (n-1)n/2

Теперь мой вопрос ... откуда берется 1?Я думал, что это было n-1 + n-2 +... + n.

Более того, я действительно не понимаю, как придумать (n-1)n/2.
Это, очевидно, то, что я должен придумать в среднесрочной перспективе,и, глядя на это, (n-1)n/2 не приходит интуитивно ... Я понимаю, как придумать T(n) = (n-1) + (n-2) и т. д., я думаю ...

Может кто-нибудь объяснить мне это в непрофессионалахусловия, чтобы я мог придумать ответ, как этот для моего промежуточного завтра?

Ответы [ 4 ]

4 голосов
/ 08 февраля 2012

Во внутреннем цикле j работает от i+1 до n, то есть до значений n-i. Так что в целом, есть 

sum_{i = 1 to n-1} (n-i)

шагов, (n-1) + (n-2) + ... + (n - (n-1)) = (n-1) + (n-2) + ... . 1.

Теперь для суммы первых k положительных целых чисел есть замкнутая формула, это 

k*(k+1)/2

Здесь k = n-1.

Чтобы разработать формулу для суммы первых k положительных целых чисел, есть несколько хороших способов, как упомянуто в ответ Роберта Кинга Предположительно, Гаусс разработал это первым способом, когда ему было пять лет, и учитель дал ученикам задачу вычислить сумму целых чисел от 1 до 100 в надежде провести несколько спокойных минут. Лучше посмотреть, если устроен так: 

  1   +   2   + ... + (n-1) +   n
  n   + (n-1) + ... +   2   +   1
----------------------------------
(n+1) + (n+1) + ... + (n+1) + (n+1) = n*(n+1)
1 голос
/ 09 февраля 2012

Один из способов сделать это:

сумма = 1 + 2 + 3 + 4 + ... + п

2 * сумма = 1 + 2 + 3 + 4 + ... + n + 1 + 2 + 3 + 4 + ... + n = 1+ (n) + 2+ (n-1) + 3 + (n-2) .. + (n) + 1

2 * сумма = 1 + n + 1 + n + 1 + n ...

2 * сумма = n (1 + n)

сумма = п * (п + 1) / 2

но более простой способ увидеть это - представить квадрат или матрицу сетки.

когда я спускаюсь к каждой новой строке, j пересекает и добавляет столбец к диагонали матрицы (так как i <= j .. мы знаем, что j не может пройти диагональ). Это означает, что все операции являются комбинацией (i, j) на одной стороне диагонали матрицы. Таким образом, количество операций составляет половину площади всей матрицы. если матрица представляет собой матрицу n * n, то мы имеем около n * n / 2 площади (но поскольку мы не можем посчитать диагональ вдвое больше, чем она есть на самом деле n * (n-1) / 2 </p>

0 голосов
/ 08 февраля 2012

Серия переходит от (n-1) к (1) [(n-1), (n-2) ... (n- (n-1))] проверьте сумму ряда здесь , чтобы узнать, как она была получена. Это довольно легко понять.

0 голосов
/ 08 февраля 2012

ОК, подумайте так: 

When i = 1, inner loop runs (n - 1) times [j = 2 to n]
When i = 2, inner loop runs (n - 2) times [j = 3 to n]
When i = 3, inner loop runs (n - 3) times [j = 4 to n]
....
When i = k, inner loop runs (n - k) times [j = k + 1 to n]
...
When i = n - 1, inner loop runs (n - (n - 1)) = 1 time [j = n to n]

Теперь подведите их: 

(n - 1) + (n - 2) + (n - 3) + ... + 1 = n(n - 1) / 2

В худшем случае exchange будет выполнено n(n - 1) / 2 раз.1009 *

...