• Здраво и добредојдовте на форумот на IT.mk.

    Доколку сеуште не сте дел од најголемата заедница на ИТ професионалци и ентузијасти во Македонија, можете бесплатно да се - процесот нема да ви одземе повеќе од 2-3 минути, а за полесна регистрација овозможивме и регистрирање со Facebook и Steam.

Најди максимален елемент во stack

  • Ја почнал/а темата
  • #1

pandora

Intern
24 февруари 2010
13
0
Скопје
Дали е можно да се најде максималниот елемент во податочна структура стек и да има сложеност О(1) во најлош случај? Значи јас најдов едно решение со користење на два стека, во првиот каде што се сместени елементите , се вадат еден по еден елемент со pop () која е со константна сложеност, користам помошна променлива maxValue во неа од првиот стек после сместувам во другиот на крај и правам споредби. На крај во таа променлива ќе биде максималната вредност. Но бидејќи го одминувам целиот прв стек значи сложеноста ќе биде О(n) под претпоставка дека има n елементи, или грешам?
 

DaciSS

Gaining Experience
3 јануари 2008
949
288
San Francisco
www.linkedin.com
Епа ќе користиш цело време 2 стека, така што 1 стек цело време треба да ти е подреден и најголемиот елемент да е на врв. Во случај кога додаваш нов елемент ако новиот е најголем ондак го ставаш во подредениот стек, ако не ондак треба да ги извадиш елементите од подредениот стек, да ги ставиш во другиот и на новиот ел да му најдеш место. На тој начин ќе да се вади маx ел сo 0(1), али внесување на нов ел не ти е веќе O(1), него најлош случај ќе испадне 0(2n) ако треба сите ел да ги извадиш од првиот да ги ставиш во вториот и пак да ги вратиш во првиот.

Така да исто искача како твојата логика. Ако тераш по оваа логика имаш О(1) вадење, ако е само тоа услов, а не е битна сложеноста на ставање.
 

ChemicalAngel

Gaining Experience
24 ноември 2008
812
222
Да не си грешка, максимален елемент во податочна структура heap има сложеност O(1), во stack по она што го кажуваш сложеноста е O(n).
 
  • Ја почнал/а темата
  • #4

pandora

Intern
24 февруари 2010
13
0
Скопје
Ако претпоставиме дека стекот е сортиран тогаш ок последниот внесен елемент ќе биде максимален и тогаш вадењето на тој елемент ќе има сложеност O(1), ама кога не е сортиран стекот... Мислам дека тогаш веќе е О(n) мора да се измине целиот прв стек да се направат споредби. Може грешам затоа пишав
 

ChemicalAngel

Gaining Experience
24 ноември 2008
812
222
Не грешиш, stack не е податочната структура што ти треба за O(1), ти треба heap. Stack не имплементира никаква логика само се прави pop и push, додека кај heap коренот на дрвото е секогаш max/min елемент (тоа зависи како ти ќе го одредеш). И кога сакаш максимален за O(1) го земаш само првиот елемент и ете операција O(1).
А можеш да имлементираш и stack така да имаш еден помошен објект во кој ќе чуваш вредност и секогаш при внесување на елемент да прави споредба и да го зачувува максималниот тој објект. Само при вадењето на елементите ќе треба да смислиш како да го изведеш, за да не ти испадне дека максимален во stack-от е 3 а него во stack-от го нема.
 
  • Ја почнал/а темата
  • #6

pandora

Intern
24 февруари 2010
13
0
Скопје
Да така е, проблемот е што најдов пример задача од испит со такво барање па ме збуни за момент.
Btw фала на размислувањето
 

Нови мислења

Последни Теми

Статистика

Теми
43,698
Мислења
848,930
Членови
29,431
Најнов член
XFXRX580
На врв Дно