Дискретна математика Big-O нотация Сложност на алгоритъма

Вероятно мога да разбера част b, ако можете да ми помогнете да направя част a. Гледам този и подобни проблеми цял ден и просто имам проблеми да разбера какво да правя с вложените цикли. За първия цикъл има n итерации, за втория има n-1, а за третия има n-1.. Правилно ли мисля за това?

Разгледайте следния алгоритъм,
който приема като вход поредица от n цели числа a1, a2, ..., an
и произвежда като изход матрица M = {mij}
където mij е минималният член< br> в последователността от цели числа ai, a + 1, ..., aj за j >= i и mij = 0 в противен случай.

инициализирайте M така, че mij = ai, ако j >= i и mij = 0

for i:=1 to n do
    for j:=i+1 to n do
        for k:=i+1 to j do
            m[i][j] := min(m[i][j], a[k])
        end
    end
end
return M = {m[i][j]}

(a) Покажете, че този алгоритъм използва Big-O(n^3) сравнения за изчисляване на матрицата M.
(b) Покажете, че този алгоритъм използва Big-Omega(n^3) сравнения за изчисляване на матрицата M.

Използвайки това лице и част (a), заключете, че алгоритъмът използва Big-theta(n^3) сравнения.


algorithm matrix math big-o complexity-theory
person kkm    schedule 14.10.2012    source източник

Отговори (2)


arrow_upward
5
arrow_downward

В част A трябва да намерите горна граница за броя на min операции.

За да направите това, е ясно, че горният алгоритъм има по-малко min операции от следното:

for i=1 to n
  for j=1 to n //bigger range then your algorithm
    for k=1 to n //bigger range then your algorithm
        (something with min)

Горното има точно n^3 min операции - следователно във вашия алгоритъм има по-малко от n^3 минути операции.

От това можем да заключим: #minOps <= 1 * n^3 (за всяко n > 10, където 10 е произволно).
Според дефиницията на Big-O това означава, че алгоритъмът е O(n^3)

Казахте, че можете да измислите Б сам, така че ще ви позволя да опитате :)

намек: средният цикъл има повече итерации от for j=i+1 to n/2

person amit    schedule 14.10.2012
comment
Благодаря! Това има много повече смисъл от всеки друг пример от учебника. Сега, за част b. Като гледам подсказката ви, ако погледна само първата половина от термините, броят на операциите ще бъде по-малък, но алгоритъмът все още ще изпълнява Cn^3 операции, където C ‹=1. Следователно алгоритъмът е Big-Omega(n^3). Вярно ли е? - person kkm; 14.10.2012
comment
@helmeplease: Идеята е правилна, но има още стъпки, които трябва да се извършат, за да я покажете, след това направо напред, ако имате нужда от нея официално. Опитайте, използвайте същия подход, който използвах, за да покажа големия O и след няколко опита съм сигурен, че ще стигнете до там. - person amit; 14.10.2012
comment
Трябва ли да кажа точно колко операции има този нов алгоритъм или мога да кажа Cn^3 операции, където C ‹=1? Това е, с което имам най-големия проблем - изчисляването на броя на операциите, когато не е толкова просто, както в примера, който си дал. - person kkm; 14.10.2012
comment
Ако можете да покажете някакво произволно C*n^3, това е ОК, но трябва да дадете конкретно C и да покажете защо това C е правилно. Ако можете да докажете, че съществува такъв C също е добре. - person amit; 14.10.2012
comment
Как бих показал това за произволен Cn^3, ако не знам точния брой операции в моя алгоритъм? Не мога да бъда 100% сигурен, че minOps ›= Cn^3 за произволен C, нали? - person kkm; 14.10.2012

arrow_upward
0
arrow_downward

За всяка итерация на външния цикъл двата вътрешни вложени цикъла ще дадат n^2 сложност, ако i == n. Външният цикъл ще се изпълнява за i = 1 to n. Така че общата сложност би била поредица като: 1^2 + 2^2 + 3^2 + 4^2 + ... ... ... + n^2. Тази сумирана стойност е n(n+1)(2n+1)/6. Пренебрегвайки членовете от по-нисък ред на този сумиращ член, в крайна сметка редът ще бъде O(n^3)

person taufique    schedule 14.10.2012