200918_TIL

Today I learned

• bubbleSort 알고리즘 & 시간 복잡도 ( Toy problem )
• self guided Lesson
  • CS Basic
  • Data structure
  • OOP

BubbleSort 알고리즘 & 시간복잡도

@@ 오늘은 토이 문제를 풀다가, 해당 알고리즘에 대한 시간 복잡도와 최적화 코드 적용시의 시간 복잡도에 대한 궁금증이 생겨 헬프데스크에 질문을 올렸다.

기존 레퍼런스 코드 및 내가 구현한 알고리즘 다 big O 표기법으로 표현하면 O(n^2)의 시간복잡도를 갖는다는 것을 이해했으나 최적화 코드 구현시의 시간 복잡도가 어떻게 달라는지 헷갈렸던 탓이다.

답변을 통해,
big O 표기법이 다시금 최악의 경우를 가정하는 시간복잡도 표기법임을 다시 정리했고,
이번 알고리즘의 최적화 코드는 정렬 알고리즘의 시간복잡도엔 큰 영향을 주진 않지만, 시간복잡도가 달라지지 않았다고 해서 최적화 코드가 의미가 없는 것은 아니며, 최적화를 진행할 때 비용 대비 효과를 염두하고 진행해야 한다는 점. 또 시간복잡도만이 절대적 기준이 될 순 없다는 점을 느낄 수 있었다.

또 입력값에 어떠한 패턴을 가질 때 최적화 코드가 갖는 유의미성에 대해서 다시금 생각해볼 수 있었다. (아마도 패턴을 갖는다면, 최적화코드로 시간복잡도를 낮출 수 있겠지)

아직은 내가 서비스 알고리즘을 개발하는 입장도 아니고, 시간복잡도가 갖는 의미와 중요도가 머리로만 중요하다! 이렇게 이해하는 느낌이지만, 나중을 위해서 이런 훈련 및 사고를 하는 습관을 들이는 게 중요할 것 같다. 모두 다 이해하고 실감하며 진행하면 가장 좋겠지만, 꼭 그게 아니더라도 노력하는 것만으로 얻는 것도 있다고 믿는다.

Data structure

Queue

• 순환큐 (circular Queue)
• 우선 순위큐

Linked List

• 순환 연결 리스트

hash Table

• [키, 밸류값]으로 묶은 값이 해시 테이블에 들어감
• 키 -> 해시함수를 이용한 해시값으로 변환하는 해시 함수
• 해시 충돌
• 암호화와 해시함수는 다르다
• 해시를 한 뒤 input으로 돌아갈 수 없음

Tree

• 계층적 형태

• 많은 양의 정보 정리시 유용

• sub-tree 가 반복되는 tree 구조-> recursion 을 활용하면 메소드 구현에 용이

big O notaion

• 알고리즘 성능 측정방법의 중요성

OOP

• new 연산자를 붙이면 해당 함수는 생성자 함수로 동작
• prototype 기반 언어 자바스크립트
• 객체는 메소드와 속성을 상속받기 위한 템플릿으로서 프로토타입 객체를 가진다
• 프로토 타입 객체도 또 다시 상위 프로토 타입 객체로부터 상속 받을 수 있다 (프로토타입 체인)
• 상속되는 속성 메소드는 객체 생성자의 prototype 속성에 정의 돼있다.
• 함수를 정의하면 prototype 객체도 같이 생성된다
• 또한 생서자 함수로 생성된 객체는 __proto__ 라는 인터널 슬롯을 가진다.
• 인터널 슬롯은 상위의 prototype Object를 가리킨다.
• porotype 객체는 일반적 객체와 같고, 디폴트 속성으로 constructor, __proto__를 가지고 있다.

class Person{
    constructor(name){
        this.name = name
    }
}

person = new Person('elin');

Person.prototype.constructor //class Person
person.prototype.__proto__ //Object

Person.constructor // Function
Person.__proto__ //f anonymous (Fuction 의 프로토타입)
Person.constructor === Person.__proto__.constructor

Function.__proto__ //Object

person.__proto__ //Person.prototype
Person.prototype.__proto__ //Object

• 함수 객체도 역시 __proto__를 가진다. (객체이기 때문에)
• 클래스는 prototype과 __proto__ 를 가진다.

• Instantiation Pattern (4-way)

  1) Functional

  내부에 리터럴 객체 선언하고 프로퍼티 및 메소드를 선언한뒤 리턴하는 방식

  2) Functional Shared

  마찬가지로 프로퍼티는 함수 안에 리터럴형태로 선언하고, 메소드는 함수 밖 전역 변수로 선언해서 메소드를 담는다. (Functional과 비교하여 메소드의 재사용성이 늘어나게된다)

  3) Prototypal

  마찬가지로 바깥에 메소드를 선언하여서 , Object.create()를 이용하여 함수(클래스로 사용하는) 내부에서 복사하고 프로퍼티를 할당해준다.

  이렇게 하면 Deep copy로 원본에 영향을 주지 않고, 변경하여 사용 가능하다.

  4)Pseudoclassical

  이전 방법들과 달리 new 연산자를 이용하여 생성자 함수를 이용한 방법이다.

  함수 객체가 생성자로 사용될 때, 만들어진 인스턴스들끼리 prototype 이라는 숨김 프로퍼티를 공유하게 된다. 이를 통해서 상속을 구현할 수 있다.