removeFirst 함수의 시간복잡도에 대해

removeFirst() : O(N)

오늘 프로그래머스 "두 큐 합 같게 만들기" 문제를 푸는도중에.. '실패 ( 시간 초과 )'

원인은 반복문 내에 있던 "removeFirst()" Array에서 제일 앞 원소를 삭제하면서 해당 원소를 리턴해주는 유용한 녀석..

이지만! 시간 복잡도가 O(n)이라니..
swift의 배열을 removeFirst()와 append()를 사용해 파이썬의 덱처럼 사용해와서 나도 모르게 '그냥 앞에있는거 하나 빼는거니까 O(1) 아닌가?'라고 생각,,

다시 배열을 생각해보니 앞에있는걸 빼버리면 index 0 에 위치한 값이 사라지게 되므로 모든 원소들이 앞으로 한칸씩 움직일것 같았다.

생각 -> 배열의 index 0 의 원소를 꺼내고 배열을 순회하면서 한 칸씩 앞으로 이동하므로 배열을 재생성하게 됨 -> O(N)의 시간복잡도

apple/swift 깃허브 문서

extension Collection where SubSequence == Self {
/// Removes and returns the first element of the collection.
///
/// The collection must not be empty.
///
/// - Returns: The first element of the collection.
///
/// - Complexity: O(1)
@inlinable
@discardableResult
public mutating func removeFirst() -> Element {
  // TODO: swift-3-indexing-model - review the following
  _precondition(!isEmpty, "Can't remove items from an empty collection")
  let element = first!
  self = self[index(after: startIndex)..<endIndex]
  return element
}

Developer Documentation

Array와 Array.Subsequence가 같다면 O(1) 다르면 O(n)일 것이다

Array<Any>.self != Array<Any>.SubSequence.self 

실제로 같지 않음!
애플 개발자 문서의 Array 탭 하위의 removeFirst() 역시 O(n)으로 표기되어있다..!

찾아본 결과 배열의 첫번째 인자를 리턴하고 배열을 새로 압축하기 때문이라고 함..
생각해본 그림이 맞았던것 같다.. 다만 원소가 사라지는 부분에 대해선 메모리 구조를 더 찾아봐야겠다..

문서를 읽어보며
Collection을 채택하는 타입들 중 RandomAccessCollection 프로토콜, RangeReplaceableCollection 프로토콜 등 어떤 프로토콜을 채택하느냐에 따라 시간복잡도가 다른것을 확인할 수 있었다..

앞으론 요소에 대한 접근과 작동을 생각해보며 알고리즘을 고민해보자! (혼잣말)

참조
https://developer.apple.com/documentation/swift/array
https://developer.apple.com/documentation/swift
https://github.com/apple/swift
https://forums.swift.org/t/array-removefirst-is-o-n/44430
https://forums.swift.org/t/sequence-removefirst-int-inconsistency/23739

---

p.s. 임시저장하고 쓰고 지우고 또 다시 옮기다 보니 내 첫 velog 글이 뜬금없는 주제로 시작...