인프런 워밍업 클럽2 cs <day13>
알고리즘퀵정렬퀵정렬은 병합정렬과 같이 분할 정복 알고리즘으로~재귀를 사용한다.피벗 : 첫 피벗은 첫번째 인덱스left, right : 각자 왼쪽 오른쪽 끝에 있는 것rightStartIndex : 왼쪽으로 이동, 피벗보다 작은 값을 만나면 멈춘다.leftStartIndex : 오른쪽으로 이동, 피벗보다 큰 값을 만나면 멈춘다.rightStartIndex와 leftStartIndex가 조건에 의해 멈췄을 때 두값을 스왑하여 바꾼다.rightStartIndex와 leftStartIndex가 지나칠 때 멈춘다. rightStartIdnex값과 피벗 위치를 바꿔 피벗은 5, rightSI는 4가된다.-> 피벗을 기준으로 왼쪽은 피벗보다 작은 값, 오른쪽은 피벗보다 큰 값으로 나뉘게되고나눠진 그 배열을 또 위에서 정렬한 것처럼 반복피벗을 기준으로 배열을 반으로 나눈다 -> O(log n) 이작업을 데이터 n개만큼 반복해야하므로 n을 곱한다. -> O(nlog n)최악의 경우 : 피벗이 가운데가 아니고 한쪽으로쏠림 -> O(n^2)근데 평균성능보는거라 Θ(nlogn) Θ는 세타병합이랑 퀵이랑 비교했을 때 병합이 더 좋아보이지만 퀵은 적은비교 적은 메모리사용으로 퀵이짱인것이다~ 운영체제주변장치내부구조를 보자면...레지스터들 : 입출력 작업 시에 데이터를 저장하는 역할 이 값들은 메모리에 이동되기도 한다.세가지 버스를 따로 받을 수있다. Address, Data, Control캐릭터 디바이스와 블록 디바이스 데이터 전송단위가 캐릭터(글자)이거나 블록 단위캐릭터 디바이스 특 : 데이터 전송단위가 캐릭터로 상대적으로 작다. 마우스,키보드블록 디바이스 특 : 데이터 전송단위가 블록단위로 캐릭터보다는 크다. 하드디스크 ,ssd 주변 장치들은 메인보드 내의 버스로 연결된다. 하나의 버스였지만 I/O작업을 수행하기위해서 입출력 제어기와 여러 개의 버스가 추가됐다.(CPU가 I/O 작업때문에 다른작업을 못했기때문)CPU는 I/O작업을 만나면 입출력 제어기에게 입출력 작업을 맡기고 다른 작업을 실행하러간다.입출력제어기 - 시스템버스와 입출력 버스로 구분 시스템버스는 CPU, 메모리가 사용하고 입출력 버스는 주변장치들이 사용입출력버스 - 고속입출력, 저속입출력->속도차이로인한 병목현상을 해결그래픽카드는 주변 장치이지만 대용량의 작업을 실행하기때문에 시스템 버스를 사용한다.입출력 제어기는 여러 주변장치를 처리하는데 입출력 버스에서 온 데이터를 메모리로 옮겨야한다. -> 입출력 제어기가 메모리 접근을 위해 CPU를 거쳐야되는데 CPU 도움없이 DMA제어기를 추가시켰다.Direact Memory Access : cpu없이 입출력 제어기가 메모리에 접근할 수있도록 한다.Memory Mapped I/O : cpu와 DMA 제어기가 사용하는 메모리 영역을 나눠 혼돈을 막는다.마우스광학마우스 , 키보드아래 카메라를 통해 초당 1500회를 찍어 디바이스 컨트롤러 안 DSP로 보낸다.x,y 축 좌표 움직임을 캐치한다.DSP가 움직임과 클릭을 감지했을 때 cpu에게 인터럽트를 발생시켜 마우스 드라이버가 동작해 데이터를 읽어간다.마우스 드라이버는 운영체제에게 이벤트 신호를 주고 운영체제는 이 이벤트를 foreground 애플리케이션으로 전달해준다.해당 애플리케이션은 받은마우스 이벤트를 처리한다. 하드디스크하드시스크 구조플레터 : 플레터는 여러개의 트랙으로 구성되었고 표면을 자성을 띈다. n극일경우 0, s일경우 1스핀들 : 플레터 자기화된 원판으로 이뤄졌다. 디스크암이 읽기/쓰기 헤드로 플레터의 표현을 read헤드 : 헤드는 여러 개 있고 항상 같이 움직인다. 이 헤드들은 여러 개의 플래터를 가리키게 된다.실린더 : 여러개의 같은 집합의 플래터에 있는 트랙의 집합을 실린더라고한다.트랙 : 여러 개의 섹터로 나뉜다.섹터 : 하드디스크의 가장 작은 단위유저프로세스가 하드 디스크의 특정 섹터에 접근하고 싶어서 이러한 요청을 보낸다.실린더 c로 가서 트랙 b에 있는 섹터 d를 읽어라seek : 디스크암은 헤드를 실린더 c로 이동seek time : 헤드를 실린더로 이동시키는데 시용하는 시간 트랙b의 섹터가 d 가 헤드에 닿을 때가지 스핀들ㅇ르 회전시키고 헤드에 섹터d가 읽히면 작업이 끝난다.다른 전자 기기 작업시간은 ns 단위지만 헤드 이동시간은 ms라 하드디스크가 느리다. 플레시 메모리(ssd)와 하드디스크자성을 띄는 하드디스크는 자석을 가져다대면 망가지지만 플레시 메모리는 그러지 않고 전기적으로 데이터를 읽어 조용하다.스핀들과 같은 회전축때문에 충격에 약한 하드디스크ssd 단점 : 특정 지점에 데이터를 썼다면 덮어쓰기가 불가능하다. 똑같은 지점에 데이터를 쓰고 싶으면 지워야하지만 메모리 지우기 기능 횟수가 정해져있다. ->똑같은 구간에 지우기 쓰기를 여러 번할 경우 망가질 수있다.
