Софтуерно Инженерство
Loading...
+ Нов въпрос
zh.stoqnov avatar zh.stoqnov 103 Точки

Homework Data Structures, Algorithms and Complexity

Здравейте колеги!

Отварям темата, защото смятам че за всички ни ще е полезно да обменим някакви решения, кой какво е разбрал и прочие. Аз лично не знам доколко ми е станало ясно всичко, което бе засегнато на първата лекция (към момента даже си мисля че не съм особено в час). Прилагам решенията си, до които аз стигнах - ще се радвам ако има критики и преди всичко обяснение кое, защо и как не е или е така. smiley

Домашно

3
Структури от данни и алгоритми 30/06/2015 18:14:56
krach avatar krach 65 Точки

Честно казано и аз не разбрах кое е правилно. Във файла с домашното пише необходимото време. Така както го разбирам аз е, времемето от стартирането до завършването на даден метод.

0
mitkoofc avatar mitkoofc 6 Точки

Здравей!

Първо да кажа, че и аз много много не разбрах материала от последната лекция и затова и аз ще бъда много доволен, ако някой сподели своите мнения или решения. Колкото до твоето домашно, според това което съм разбрал, имам следното предложение за поправка: 

- На 4 проблем - за да се намери средната сложност, не би ли трябвало да използваме формулата (worstCase-bestCase)/2, вместо да делим получената ти сложност на 6. И отделно, 2/3*n+2/3 е линейна функция, а не логаритмична.

На останалите смятам, че отговорите ти са правилни. И все пак отново казвам, че не съм от най-разбралите и е много вероятно да греша. Затова много се извинявам, ако съм допуснал грешки.

Поздрави! smiley 

3
dim4o avatar dim4o 289 Точки

По моите разсъждения за Remove(int index) f(n) и О(f(n)) трябва да са еднакви в best, worst and average case, защото броят на операции е абсолютно еднакъв в тази имплементация. От тази гледна точка аз не разбирам тези изчисления. Какъв според теб трябва да е best case за Remove? Може би приемаш копирането на масив за константа ако той е с един елемент? Това с логаритъма също не го разбирам как е получено. Би ли обяснил логката?

2
mitkoofc avatar mitkoofc 6 Точки

Така тук си прав. За всички стойности на n (дължината на масива), броят на извършените операции е функция на n, която със сигурност е линейна и принадлежи на O(n). Просто в best case-a лесно можем да заместим n и да открием точния брой операции, като те пак си принадлежат на О(n). Но иначе наистина не виждам смисъла в това да заместваме за различните n и да търсим някакви конкретни решения, като те винаги ще са от О(n). От друга страна, ако реално се търси времето за изпълнение, вече ще има смисъл да ги разглеждаме по отделно, за да получим някакви различни отговори. Но нека някой по-компетентен или разбрал да се изкаже, защото като гледам много много не сме усвоили материала. Поздрави :)

 

1
dim4o avatar dim4o 289 Точки

Според мен 'the expected running time' трябва да се разбира по-скоро като 'сложност по време', защото O(f(n)) (Big O notation), трябва да е точно това. И разбира се best/worst case не трябва да зависят от опредлени стойности на входа. Случая с домашното според мен е такъв, че изглежда токова тъпо, че всички се чудим дали не сме рабрали нещо не както трябва.

3
30/06/2015 22:40:40
krach avatar krach 65 Точки

За Remove метода и съответно Best Case - трябва да е първия елемент демек на индекс 0. Понеже за да изтрие нещо то метода трябва да обходи целия масив и в най - добрия случай ( Best Case ), това обхождане ще намери търсения за изтриване елемент още на първата итерация. В най - лошия случай този елемент ще е последен и ще трябва да обходим всички елементи преди това. За среден вариант предполагам трябва да е някой елемент в средата. Сложността е линейна в случая.

0
01/07/2015 15:03:14
Petar_Ivanov avatar Petar_Ivanov 27 Точки

Ето го и моето домашно. Различава се малко от вашите, но като цяло и аз не мога да кажа, че моето е вярно просто така ги виждам нещата. Ако имате желание прегледайте и аз ще се радвам на обратна вразка.

0
DNikolov avatar DNikolov 12 Точки

За тази операция

this.arr = newArr; // n*2

броя необходими инструкции е константа тоест сложността е O(1). Тук масива не се копира елемент по елемент а се копира само референция към него. Също не знам защо и в двете домашни до момента за копирането на масива се пишат 2*n операции като те са само n всъщност.

5
Petar_Ivanov avatar Petar_Ivanov 27 Точки

Благодаря за обратната връзка.

За копирането на масива и аз се чудех много, но не потърсих достатачно много в интернет и се оказа прав. Ето една статия (специално за python) и един въпрос в stackoverflow за C#.

0
02/07/2015 12:53:48
nickpanaiotov avatar nickpanaiotov 21 Точки

Това което си дал за python си важи само за python за друг език може да е друга имплементацията.

1
meitriks avatar meitriks 2 Точки

Здравейте, 

Ето я и моята версия на домашното. Не съм много на ти с нещата, но така ги виждам. Приемам всякакви градивни критики и коментари. :) 

http://pastebin.com/JbcgXm8Z

Поздрави!

 

1
02/07/2015 13:19:51
mihayloff14 avatar mihayloff14 825 Точки

Задачи 2,3,4 мисля че имат една и съща сложност и няма много разлика между тях, защото метода, за който става въпрос в тях е Remove(index), а това което той прави е да вземе лявата част от масива преди дадения индекс и дясната след него и да ги копира в друг масив. Следователно, мисля че сложността е N - 1 + C или O(N) независимо от случая който има (Worst, average, Best). Някой да е измислил друго решение на този проблем?

Всъщност, сега виждам и че другите методи, които ползват Remove(index) по тази причина също би трябвало да имат сложност O(N). Единствено методите First, Last, Length имат сложност O(1), защото просто достъпват елемент без да итерират нищо.

Ето моето решение на задачата, очаквам коментари, защото не съм убеден, че това е реалното решение на задачите напълно:

http://pastebin.com/AdXFuWid

7
Karlie avatar Karlie 438 Точки

Малко полезно инфо (естествено, трябва човек да е осмислил нещата, но понякога трябва и бърза референция) .

14
03/07/2015 00:38:17
pafkuneca avatar pafkuneca 14 Точки

Съгласен съм с mihayloff14 сложността трябва да е O(n) за Remove, понеже стъпките са размера на старият масив - 1 и е едно и също за Worst, Average i Best Case.

2
Ventsislav avatar Ventsislav 343 Точки

Здравейте колеги, ето го и моето домашно. Ще се радвам ако някой го погледне и даде feedbacksmiley

2
pepster avatar pepster 69 Точки

Здравей, погледнах ти домашното:) 

 Аз лично не откривам грешки. Моите разсъждения са аналогични.

1