Попаднах на тази статия относно времевата сложност на динамичните масиви, която изясни много. Имам обаче въпрос, базиран на казус. Да кажем, че имам динамичен масив, който има общо 6 елемента и да предположим, че 4-тият елемент е премахнат. В този случай сложността на изтриването ще бъде O(n-index), което ще бъде O(6-4) = 2, тъй като последните два елемента ще трябва само да се придвижат нагоре. Дали това е правилно ? Имам статии, които дават най-лошия случай на сложност, казвайки, че ако най-горният елемент бъде премахнат, тогава времевата сложност ще бъде O(n). Не можах да намеря нищо, което да говори за премахване/вмъкване на елемент от/в центъра.
Времева сложност - Вмъкване на елемент в средата на динамичния масив
Отговори (1)
Вашият анализ на броя елементи, които трябва да бъдат преместени, е правилен. Въпреки това, в нотация с голямо О, това все още е O(n). Ако имате n елемента в списъка и премахнете нещо от средата, ще трябва да преместите *0,5 * n* елемента. Но когато имаме работа с голямо O, ние изпускаме всички постоянни множители, така че това е само O(n).
person
Oliver Dain
schedule
03.07.2015
Не съм сигурен какво имате предвид под ‹blockquote› Ако имате n елемента в списъка и премахнете нещо от средата, ще трябва да преместите 0,5 * n елемента ‹/blockquote› Как попаднахте 0,5 * n?
- person James Franco; 04.07.2015
Добре, благодаря, че изясни това. Как бихте написали времева сложност за премахване на 4 елемента от общо 6 елемента, без да пренебрегвате постоянния член? Ще бъде ли
O(6 * 4/6)? Това ще ми даде 4, което е грешно, очаквах 2
- person James Franco; 04.07.2015
Говоренето за сложност за фиксиран брой елементи няма смисъл. Big-O е всичко за това как изчисляването на времето се променя като се променя размерът на входа.. За вашия въпрос (4 се премахват от масив от 6), че може да означава, че винаги премахвате последните 4 елемента, без значение колко голям е масивът, в който случай е O(1), или може да означава, че винаги премахвате последните 2/3 от масивът, в който случай е O(n) или може да означава, че винаги премахвате всички елементи освен първите два (O(n)) отново) и т.н. .
- person Oliver Dain; 04.07.2015
