단일 링크 된 목록 의사 코드 합계 특정 요소

Question

단일 링크 된 목록에 대해 의사 코드를 작성했습니다. 함수는 이전 요소의 키 값으로 키 (k)가 발생할 때마다 증가시켜야합니다. 유일한 예외는 첫 번째 요소 (변경되지 않음)입니다.

List-Increase-Key(L,k) 
    x = L.head 
    k = L.head 
    while (x.key != k and x != NIL) 
     prex = x.key 
     x = x.next 
     if x.key == k 
      x.key = x.key + prex 

전체 목록을 한 번 통과하기 때문에 실행 시간은 O (n)라고 생각합니다. 내 시간 복잡도 추정치가 정확한지, 아니면 시간적 복잡성 추정치가 정확하지 않거나 덜 효율적인지 궁금합니다. 아니면 내 아이디어가 쓰레기라고 생각하고 충돌을 당하고 무서워 질 것입니다. 들러 주셔서 감사합니다.

Answer 1

단일 탐색이 수행되므로 실행 시간은 분명히 O (n)입니다.

하지만 코드에 일부 불일치가 있습니다.

while (x.key != k and x != NIL) 

위의 성명에서 NIL 검사 조건 "x.key! = K"을 선행해야한다.