Здравейте колеги!
Отварям темата, защото смятам че за всички ни ще е полезно да обменим някакви решения, кой какво е разбрал и прочие. Аз лично не знам доколко ми е станало ясно всичко, което бе засегнато на първата лекция (към момента даже си мисля че не съм особено в час). Прилагам решенията си, до които аз стигнах - ще се радвам ако има критики и преди всичко обяснение кое, защо и как не е или е така. 
Честно казано и аз не разбрах кое е правилно. Във файла с домашното пише необходимото време. Така както го разбирам аз е, времемето от стартирането до завършването на даден метод.
Здравей!
Първо да кажа, че и аз много много не разбрах материала от последната лекция и затова и аз ще бъда много доволен, ако някой сподели своите мнения или решения. Колкото до твоето домашно, според това което съм разбрал, имам следното предложение за поправка:
- На 4 проблем - за да се намери средната сложност, не би ли трябвало да използваме формулата (worstCase-bestCase)/2, вместо да делим получената ти сложност на 6. И отделно, 2/3*n+2/3 е линейна функция, а не логаритмична.
На останалите смятам, че отговорите ти са правилни. И все пак отново казвам, че не съм от най-разбралите и е много вероятно да греша. Затова много се извинявам, ако съм допуснал грешки.
Поздрави!
По моите разсъждения за Remove(int index) f(n) и О(f(n)) трябва да са еднакви в best, worst and average case, защото броят на операции е абсолютно еднакъв в тази имплементация. От тази гледна точка аз не разбирам тези изчисления. Какъв според теб трябва да е best case за Remove? Може би приемаш копирането на масив за константа ако той е с един елемент? Това с логаритъма също не го разбирам как е получено. Би ли обяснил логката?
Така тук си прав. За всички стойности на n (дължината на масива), броят на извършените операции е функция на n, която със сигурност е линейна и принадлежи на O(n). Просто в best case-a лесно можем да заместим n и да открием точния брой операции, като те пак си принадлежат на О(n). Но иначе наистина не виждам смисъла в това да заместваме за различните n и да търсим някакви конкретни решения, като те винаги ще са от О(n). От друга страна, ако реално се търси времето за изпълнение, вече ще има смисъл да ги разглеждаме по отделно, за да получим някакви различни отговори. Но нека някой по-компетентен или разбрал да се изкаже, защото като гледам много много не сме усвоили материала. Поздрави :)
Според мен 'the expected running time' трябва да се разбира по-скоро като 'сложност по време', защото O(f(n)) (Big O notation), трябва да е точно това. И разбира се best/worst case не трябва да зависят от опредлени стойности на входа. Случая с домашното според мен е такъв, че изглежда токова тъпо, че всички се чудим дали не сме рабрали нещо не както трябва.
За Remove метода и съответно Best Case - трябва да е първия елемент демек на индекс 0. Понеже за да изтрие нещо то метода трябва да обходи целия масив и в най - добрия случай ( Best Case ), това обхождане ще намери търсения за изтриване елемент още на първата итерация. В най - лошия случай този елемент ще е последен и ще трябва да обходим всички елементи преди това. За среден вариант предполагам трябва да е някой елемент в средата. Сложността е линейна в случая.
Ето го и моето домашно. Различава се малко от вашите, но като цяло и аз не мога да кажа, че моето е вярно просто така ги виждам нещата. Ако имате желание прегледайте и аз ще се радвам на обратна вразка.
За тази операция
this.arr = newArr; // n*2
броя необходими инструкции е константа тоест сложността е O(1). Тук масива не се копира елемент по елемент а се копира само референция към него. Също не знам защо и в двете домашни до момента за копирането на масива се пишат 2*n операции като те са само n всъщност.
Благодаря за обратната връзка.
За копирането на масива и аз се чудех много, но не потърсих достатачно много в интернет и се оказа прав. Ето една статия (специално за python) и един въпрос в stackoverflow за C#.
Това което си дал за python си важи само за python за друг език може да е друга имплементацията.
Здравейте,
Ето я и моята версия на домашното. Не съм много на ти с нещата, но така ги виждам. Приемам всякакви градивни критики и коментари. :)
Поздрави!
Задачи 2,3,4 мисля че имат една и съща сложност и няма много разлика между тях, защото метода, за който става въпрос в тях е Remove(index), а това което той прави е да вземе лявата част от масива преди дадения индекс и дясната след него и да ги копира в друг масив. Следователно, мисля че сложността е N - 1 + C или O(N) независимо от случая който има (Worst, average, Best). Някой да е измислил друго решение на този проблем?
Всъщност, сега виждам и че другите методи, които ползват Remove(index) по тази причина също би трябвало да имат сложност O(N). Единствено методите First, Last, Length имат сложност O(1), защото просто достъпват елемент без да итерират нищо.
Ето моето решение на задачата, очаквам коментари, защото не съм убеден, че това е реалното решение на задачите напълно:
Малко полезно инфо (естествено, трябва човек да е осмислил нещата, но понякога трябва и бърза референция) .
Съгласен съм с mihayloff14 сложността трябва да е O(n) за Remove, понеже стъпките са размера на старият масив - 1 и е едно и също за Worst, Average i Best Case.
Здравейте колеги, ето го и моето домашно. Ще се радвам ако някой го погледне и даде feedback
Здравей, погледнах ти домашното:)
Аз лично не откривам грешки. Моите разсъждения са аналогични.
Моята версия >> Homework.