Day20) Big-O

Big-O

• Big-O는 알고리즘의 시간 복잡도를 나타내는 표기법이다.
• 알고리즘의 속도는 작업을 처리하는 단계에 따라서 달라진다. (단계가 적을수록 좋은 알고리즘)
• inputData의 크기와 관계없이 동일한 수의 단계를 수행한다면 O(1)이라고 표기하고
• inputData의 크기와 비례해서 수행되는 단계가 변화한다면 O(N) 이라고 표현한다.

 

알고리즘 문제에서 시간초과가 뜨지 않기 위해서는 시간 복잡도에 대한 이해를 바탕으로 코드를 작성해야 될 것 같다..

시간초과로 프로그래머스에서 2시간 삽질하다가 머리에 쥐나서 포기했다.. 🤬

 

애플 개발자 문서에서 각 메서드의 시간복잡도를 찾을 수 있다. (맨 아래에 나옴)

 

---

Array 메서드

배열은 순서대로 저장되므로 중간에 값을 추가하거나 없애면 그 뒤의 값들을 재배치 해야되서 단계가 많아진다.

append(_ newElement: )	O(1)
append(contentsOf: )	O(M) - 입력한 시퀸스의 Elements 개수에 따라 변동
insert(_ newElement: Element, at i: Int)	O(N)
count	O(1)
subscript(_: )	O(1)
last()	O(1)
isEmpty	O(1)
popLast(), removeLast()	O(1)
remove(at: )	O(N)
removeFirst()	O(N)
contains(_:), contains(where: )	O(N)
first(where: ), firstIndex(where: ), firstIndex(of: )	O(N)
last(where: ), lastIndex(where: ), lastIndex(of: )	O(N)
enumerated()	O(N)
sort(), sorted()	O(N log N)
reverse()	O(N)
reversed()	O(1) - 새 공간을 할당하지 않고 역순으로 요소들에 대한 엑세스를 제공
shuffle(), shuffled()	O(N)
swapAt(_: _:)	O(1)

 

 

 

 

Dictionay 메서드

subscript(_:)	O(1)
count	O(1)
contain(where: )	O(N)
remove(at: ), removeValue(forKey: )	O(N)
popFirst()	평균 O(1)
reversed()	O(N)

 

 

 

 

Set 메서드

subscript(_:)	O(1)
count	O(1)
contains()	O(1)
contains(where: )	O(N)
firstIndex(of: )	O(1)

Set<>에서 contains()를 사용해서 내부에 해당 값이 있는지 확인하면 O(1)이다.

 

 

고차함수

map()	O(N)
filter()	O(N)
reduce()	O(N)

 

 

 

String

count

O(N) swift의 String 문자열 동작 방식의 차이 때문

string.count == 0 😡

string.isEmpty      😀

isEmpty는 O(1)이기 때문에 가능하면 isEmpty를 사용해보자