study/Data structure9 Linked List array list와 다르게 메모리에 저장될 때 나란히 저장되지 않을 수 있다. 그래서 인덱스가 노드마다 지정되어있지 않음 Big(O) linked list에서 n은 노드의 수라고 생각하면 된다. append(adding sth to the end) 노드가 몇개이든 바뀌는 게 없음 ⇒ 0(1) remove last node linked list의 연결 방향은 반대로 가는 게 불가능 예를 들면 여기서 7 노드를 없앤다면 tail을 23 노드로 옮겨야 하는데 반대로 추적할 수 없기 때문에 head부터 반복문을 돌려서 마지막 노드를 찾아야 함. n이 클수록 반복문 돌려야 하는 횟수도 늘어나기 때문에 ⇒ O(n) remove first 여기서 11 노드를 삭제한다고 하면 head를 11노드 다음에 있는 노드로 .. 2023. 7. 28. classes & pointers classes 필드와 생성자로 구성이 되어있다. 클래스는 비유를 하자면 쿠키를 만드는 틀이라고 할 수 있다. 클래스의 생성자로 클래스의 인스턴스들을 생성하여 쓸 수 있다. 자료구조에서 클래스가 어떻게 쓰이냐 예를들면 linkedList 클래스가 있으면 append, remove 와 같은 기능들이 정의되어있다. 그것을 쓰기위해 우리는 그저 linkedList 생성자를 통해 linkedList의 인스턴스를 생성해서 쓰면된다. pointers 이것을 이해하기 위해 먼저 java의 데이터 타입을 알아두면 조금 수월하다. 포인터가 아닌경우 직접 값을 넣어줄때. 기본 데이터타입(primitive type)은 값복사가 일어난다. int a = 11; int b = a; a = 22; //result // a = 22.. 2023. 7. 21. 빅오 Big(O) Big O 표기법(Big-O notation)은 코드가 얼마나 효율적으로 수행되는지에 대해 수학적으로 계산해서 나타내는 수치입니다. 코딩인터뷰 단골질문! 빅오표기법은 시간 복잡도와 공간 복잡도를 나타내는데에 쓰입니다. 시간복잡도(time complexity) - 해당 코드가 실행되는 데에 걸리는 시간 공간복잡도(space complexity) - 해당 코드가 실행될때 메모리를 차지하는 정도를 나타냄 시간 복잡도를 표기하는 3가지 방식 Ω(omega) 해당 코드의 최상 실행시간 θ(theta) 평균 실행시간을 뜻함 O(omecron) 최악 실행시간 그러므로 Big-O는 항상 최악케이스에 해당합니다. 평균빅오는 몇이냐, 최상의 빅오는 잘못된 표현. 빅오 표기법 n은 입력받은 값의 크기를 나타냄. 1. O(n.. 2023. 7. 19. 이전 1 2 다음 728x90
