-4
Big-O 표기법을 이해하는 데 문제가 있습니다. 다음은 (C++) Stack의 size() 함수 대신 사용할 수있는 알고리즘입니다. 호출 될 때 스택에 n 요소가 있다는 가정하에 실행 시간을 결정해야합니다.Big-O 표기법 : 알고리즘의 순서는 무엇입니까?
Algorithm size():
Input: none
Output: A constant value of the size of an n-element stack.
Let V be a vector of n type objects.
Let S be the name of the stack that is being operated on by this function.
K ← 0
V
while !empty()
V.push_back(top()) //Keep track of elements in V
S.pop() //Remove element from stack
K ← K + 1 //Count the size of the stack
return K //Return the size of the stack
for i ← K – 1, i > 0, i-- do
S.push(V[i]) //Retain initial contents of stack
내가 틀렸다 경우 제발 올바른 :
을 선 K ← 0, 나는 그 O (1) 연산입니다 생각합니다.
벡터 V는 O (1) 연산이기도합니다.
while 루프는 n 내용을 포함하는 스택을 비울 때까지 실행되므로 O (n) 연산입니다.
값을 V로 다시 밀어 넣는 작업은 O (n) 작업입니다.
스택에서 내용을 팝핑하는 것은 O (n) 연산입니다.
복귀 K는 O (1) 연산입니다.
for 루프는 O (n) 연산입니다.
내용을 S로 다시 밀어 넣는 작업은 O (n) 작업입니다.
Big-Oh 표기법에 대한 자세한 내용은 math.stackexchange.com 또는 cs.stackexchange.com을 참조하십시오. – Barmar
전체 벡터 또는 스택을 복사해야하는 경우가 아니면 요소를 푸시하고 팝핑하는 것은 O (1)이어야합니다. – Barmar
'for' 루프는'return' 명령문 이후이므로 결코 실행되지 않습니다. – Barmar