1

Тема: Оцінка складності алгоритмів

AAAA, завтра екзамен

Друзі, поможіть з алгоритмами)

Визначення складності. Теорію почитав: а ось з практикою не дуже)

псевдокоджу
1.

func f(int n):
    int count := 0
    for i := 0 to n:
        for j:= 0 to i:
            count++;
    print (count)

Моя версія:   O(n*n!)

2.

func f(int n):
    int count := 0
    for i := 0 to n:
        for j:=i+1 to n:
            for k:=i to j:
                count++;
    print (count)

Моя версія:   O(n*n!*log(n))

2.

func f(int n):
    int count := 0
    int m := n
    while n > 0:
        for i := 0 to n:
            count++;
        n /= 2

    print (count)

Моя версія:   O(n*something_responsible_for_while_loop) Але тут не знаю. Думав так: внутрішній цикл: зрозуміло n. Складності вкладених циклів перемножаються, тому це n треба помножити на щось що відповідає за while цикл.

while цикл:

n=5, виконається (n=5) (n=2) (n=1) 3 рази
n=10, виконається (n=10) (n=5) (n=2) (n=1) 4 рази
n=20, виконається (n=10) (n=10) (n=5) (n=2) (n=1) 5 рази


So, help me please?

2

Re: Оцінка складності алгоритмів

4

func f(int n):
    int count := 0

    for i=0; i<=n; i++:
        for j:=i; j<=n; j+=i:
            count++;
    print (count)

Моя відповідь: O(n * i_dont_know)

3 Востаннє редагувалося leofun01 (05.07.2018 20:11:57)

Re: Оцінка складності алгоритмів

Q-bart написав:

Визначення складності.
1.

func f(int n):
    int count := 0
    for i := 0 to n:
        for j:= 0 to i:
            count++;
    print (count)

Моя версія:   O(n*n!)

При великих n - O(n^2).

Q-bart написав:

2.

func f(int n):
    int count := 0
    for i := 0 to n:
        for j:=i+1 to n:
            for k:=i to j:
                count++;
    print (count)

Моя версія:   O(n*n!*log(n))

O(n^3)

Q-bart написав:

2.

func f(int n):
    int count := 0
    int m := n
    while n > 0:
        for i := 0 to n:
            count++;
        n /= 2
    print (count)

Моя версія:   O(n*something_responsible_for_while_loop) Але тут не знаю. Думав так: внутрішній цикл: зрозуміло n. Складності вкладених циклів перемножаються, тому це n треба помножити на щось що відповідає за while цикл.

O(n)

Q-bart написав:

4

func f(int n):
    int count := 0
    for i=0; i<=n; i++:
        for j:=i; j<=n; j+=i:
            count++;
    print (count)

Моя відповідь: O(n * i_dont_know)

Функція f(n) не завершиться при всіх n>=0.

+ Схоже, що код цих функцій був розроблений для { завдань, в яких потрібно вказати "що буде виведено на екран після виконання функції" }, а не для оцінки складності алгоритмів.

Подякували: Q-bart1

4

Re: Оцінка складності алгоритмів

Схоже, що код цих функцій був розроблений для { завдань, в яких потрібно вказати "що буде виведено на екран після виконання функції" }, а не для оцінки складності алгоритмів.

Так, це одне з підзавдань.

@leofun01, а можете, будь ласка, пояснити? З мене пиво (серйозно))

От напр. перша функція.

func f(int n):
    int count := 0
    for i := 0 to n:
        for j:= 0 to i:
            count++;
    print (count)

Перший ж цикл виконається n разів, другий i [ (i=0) (i=1) (i=2) (i=3) ... ] Відносно n, i - це n! ні?

Подякували: leofun011

5 Востаннє редагувалося leofun01 (05.07.2018 21:45:57)

Re: Оцінка складності алгоритмів

Q-bart написав:

От напр. перша функція.

func f(int n):
    int count := 0
    for i := 0 to n:
        for j:= 0 to i:
            count++;
    print (count)

Перший ж цикл виконається n разів, другий i [ (i=0) (i=1) (i=2) (i=3) ... ] Відносно n, i - це n! ні?

Тіло зовнішнього циклу "for i := 0 to n:" виконається (n+1) разів.
Тіло внутрішнього циклу "for j:= 0 to i:" виконається (i+1) разів за 1 крок зовнішнього циклу.
O(f(n)) == O( 1+2+3+4+5+...+(n-1)+n+(n+1) )
        == O( (n+1)*(n+2)/2 )
        == O( 1/2 * (n^2 + 3*n + 2) )
        == O( n^2 )

+

Q-bart написав:

Відносно n, i - це n! ні?

Якщо "!" - факторіал, то я не знаю про що ви.

Подякували: Q-bart1

6

Re: Оцінка складності алгоритмів

1. O(n^2), де ви там факторіал взяли? Факторіал - це коли n вкладених циклів.
Точніше, там буде рівно 2+n(n+1)/2 операцій (якщо print вважати за 1 операцію, а самі цикли не враховувати). Оскільки всі константи, менші доданки і множники відкидаються, лишається n^2.
2. O(n^3).
3. Внутрішній цикл - O(n), зовнішній виконується log2(n) разів (бо кожного разу увічі менше). Отже, O(n*log(n)).
4. Знову O(n*log(n)).

Подякували: Q-bart1

7

Re: Оцінка складності алгоритмів

Ви можете перевірити ці формули, якщо виводитимете у функціях не тільки count, а ще й count/(оцінка(n)). Буде виходити щось близьке до констант. Ось для першого: https://ideone.com/oEKyN0

Подякували: Q-bart1

8

Re: Оцінка складності алгоритмів

Правильно я зрозумів з 1 і 2 прикладу, що якщо два вкладених цикли : то n^2, якщо 3 - то n^3

9 Востаннє редагувалося leofun01 (06.07.2018 01:01:53)

Re: Оцінка складності алгоритмів

koala написав:

3. Внутрішній цикл - O(n), зовнішній виконується log2(n) разів (бо кожного разу увічі менше). Отже, O(n*log(n)).

Лише у випадку, якщо в коді

Q-bart написав:
func f(int n):
    int count := 0
    int m := n
    while n > 0:
        for i := 0 to n:
            count++;
        n /= 2
    print (count)

замість
        for i := 0 to n:
поставити
        for i := 0 to m:

koala написав:

4. Знову O(n*log(n)).

Нєа. Давайте ще раз подивимось на код:

Q-bart написав:
func f(int n):
    int count := 0
    for i=0; i<=n; i++:
        for j:=i; j<=n; j+=i:
            count++;
    print (count)


count=0
i=0
j=i        # j == 0
count++    # count == 1
j+=i       # j == 0
j<=n       # true
count++    # count == 2
j+=i       # j == 0
j<=n       # true
...
j<=n       # завжди true для всіх n >= 0

Вічний цикл.

Подякували: Q-bart1

10

Re: Оцінка складності алгоритмів

Дійсно, помилився.

11

Re: Оцінка складності алгоритмів

leofun01 написав:
koala написав:

4. Знову O(n*log(n)).

Нєа. Давайте ще раз подивимось на код:

Q-bart написав:
func f(int n):
    int count := 0
    for i=0; i<=n; i++:
        for j:=i; j<=n; j+=i:
            count++;
    print (count)


count=0
i=0
j=i        # j == 0
count++    # count == 1
j+=i       # j == 0
j<=n       # true
count++    # count == 2
j+=i       # j == 0
j<=n       # true
...
j<=n       # завжди true для всіх n >= 0

Вічний цикл.

Сорі, я помилився. Там і від 1

func f(int n):
    int count := 0
    for i=1; i<=n; i++:
        for j:=i; j<=n; j+=i:
            count++;
    print (count)

здається тут буде n*log(n)

Подякували: leofun011

12

Re: Оцінка складності алгоритмів

Так, бо гармонічні числа збігаються до логарифма.

Подякували: leofun01, Q-bart2