[TIL] 20201212

todo

• leetcode230
• leetcode66
• MachineLearning 101

What I learned

1. Arrays.sort()의 알고리즘과 복잡도

• 기본형은 DualPivotQuicksort 알고리즘을 사용하며, Object는 O(nlog(n)) 시간 복잡도를 갖는다. (최악의 경우 O(n^2))
  • 추가 공간 사용하지 않음 (in place.)
  • QuickSort 는 stable 보장하지않음. -> Object 정렬에 사용할 수 없다.
• Object: ComparableTimSort 알고리즘을 사용하며, O(nlog(n)) 시간 복잡도를 갖는다.
  • ComparableTimSort는 insertion과 merge 정렬을 사용함.
  • stable 보장함 (-> reorder되지 않음)
  • http://svn.python.org/projects/python/trunk/Objects/listsort.txt
• 참고 블로그

2. Array A 를 Array B 의 n 번째에 이어 붙이고 싶다면

A.copyInto(B, n)

• 66. Plus One 문제를 풀면서 배웠다.
• stackoverflow
• 공식사이트

  fun <T> Array<out T>.copyInto(
    destination: Array<T>,
    destinationOffset: Int = 0,
    startIndex: Int = 0,
    endIndex: Int = size
  ): Array<T>