Pw4ngC0

위 그림은 프로세스가 메인메모리에 올라갔을때 각 세그먼트를 나타낸 것이다.

stack : 함수가 호출될 때마다 스택이 사용된다. 함수에 관련 정보를 저장하는 용도를 사용된다. 함수를 호출할 때마다 함수의 지역변수들이 스택에 쌓인다.

Heap : 동적으로 할당되는 공간 ex)malloc(), alloc()

BSS : 프로그램에서 사용되는 변수들이 실제로 존재하는 곳, 초기화가 되지않은 변수들이 존재한다.

Data : 실제로 초기화가 이루어진 변수들이 존재한다.

Text : 실제로 작성한 소스코드가 들어간다. TEXT 영역의 어셈블리 코드들이 한줄씩 실행된다.

section .data

data섹션은 초기화된 데이터 또는 상수를 선언하는데 사용된다. 위에서는 문자열 변수 msg에 'Hello World'을 넣어준 것이다. .data섹션은 읽기/ 쓰기가 가능한 섹션이다. 일반적으로 정적변수와 전역변수가 저장된다.

section .text

text섹션은 실제 코드를 작성하는 section이다. 이섹션은 global _start로 시작하며 _start: 부터 코드가 실행된다.

_start: 이후부터 코드가 실행되는데 위 소스코드는 sys_write시스템콜을 하여 Hello World를 실행시키고 sys_exit(0)를 호출하여 프로그램을 끝내는 소스코드이다.

rax에 sys_call number가 들어가고, 해당 sys함수에 따라 인자들이 들어가는 것이다.

64bit syscall table 검색하면 sys_call number와 함수들 인자 레지스터 까지 리스트가 나온다.

위 소스코드에서는 mov rax,1을 통해 syscall 1번 syswrite 호출

mov rdi, 1을 통해 파일 디스크립터(fd) 1번을 넣어 stdout을 의미하게 한다.

mov rsi, msg 를 통해 rsi에 msg 포인터 변수를 넣어 해당 위치를 넣어준다.

mov rdx, 12를 통해 'Hello World' 문자열 길이를 rdㅌ에 넣어준다.

syscall -> rax시스템콜 번호와 인자들 설정 후 시스템 콜을 시켜주는 명령어이다.

rax, 60은 sys_exit 의 sys_call number이다.

rdi, 0은 sys_exit의 인자로 들어가면서 error code가 들어가야 하지만 0은 에러가 없다는 의미이다.

레지스터 : CPU 내부에 존재하는 다목적 임시 저장 공간 CPU 내부에 있으며 고속으로 데이터 처리가 가능하다.

레지스터의 종류

1. 범용 레지스터 : 범용적 즉 다양한 용도로 사용되는 레지스터이다. 범용 레지스터는 8개가 있으며, 각 32bit 크기이다.(64bit 운영체제에서는 레지스터 각 64bit크기) 주로 상수(연산 처리, 연산 결과), 주소(주소 지정, 복구 주소)등을 저장할 때 사용된다.

2. 세그먼트 레지스터 : 세그먼트란 메모리를 조각내어 각 조각마다 시작 주소, 범위, 접근 권한 등을 부여하여 메모리를 보호하는 기법이다. 또한 페이징(paging)기법과 함께 가상 메모리를 실제 물리 메모리로 변경할 때 사용된다. 16bit 크기로 6개가 있으며 메모리 영역에 대한 주소 지정을 제공한다.

3.EFLAGS(Extended FLAGS) 레지스터 : EFLAGS의 크기는 32bit이며 각 레지스터 bit마다 의미를 가지고 있다. 1 또는 0의 값을 가지며 On/Off 혹은 True/False 를 표시한다. 동작을 제어하거나 상태를 나타내는데 사용된다.

4.EIF(Instruction Pointer) : CPU가 다음으로 실행해야할 명령어가 존재하는 주소가 저장된다. CPU는 현재 명령어를 실행완료한 후에 EIP 레지스터에 존재하는 주소에 위치한 명령어를 실행하게 된다.

위의 4가지 외에도 다양한 레지스터 종류가 있다.

범용 레지스터 목록

1.EAX(Extended Accumulater Register) : 산술 연산을 수행하기 위해 사용되거나 함수의 리턴값을 전달하기 위해 사용된다. 즉, 더하기, 빼기, 비교 연산, 곱셈, 나눗셈 등을 위해 사용된다. EAX에 저장된 값을 조사하면 호출한 함수가 성공했는지, 실패했는지 여부를 판단할 수 있으며 리턴값을 알 수 있다.

2.EBP(Extended Base Pointer) : 스택 프레임의 시작지점 주소(함수 호출시 형성되는 스택 프레임의 시작주소를 가리킴), 스택 프레임이 소멸되지 않는다면 EBP의 값은 변하지 않는다.

3.EDX(Extended Data Register) : 기본적으로 EAX레지스터의 확장 개념으로 사용된다. 큰수이 곱셈과 나눗셈 연산에서 EAX레지스터와 함께 사용되고 부호 확장 명령 등에도 사용된다.

4.EBX(Exteneded Base Register) : ESI 레지스터, EDI 레지스터와 결합될 수 있으며, 이 EBX레지스터는 메모리 주소를 저장하는 용도로 사용된다.

5.ECX(Extended Counter Register) : 반복연산에서 주로 사용된다. 반복 명령어 사용시 반복 카운터로 사용된다. ECX레지스터에 반복할 횟수를 지정하고, 반복 작업을 수행한다.

6.ESI(Extended Source Index) : 데이터 조작, 복사시 Source Data의 주소가 지정된다. 일반적으로 문자열 전송 및 비교에서 사용되며 소스 문자열의 주소를 가리킨ㄴ다.

7.EDI(Extended Destination Index) : 데이터 복사시 목적지 주소 저장. 주로  ESI레지스터가 가리키는 주소의 데이터가 저장된다.

8.ESP(Extenede Stack Pointer) : 스택의 가장 높은 위치를 가리킨다. PUSH 명령어의 경우 현재 가리키는 ESP 주소에 데이터를 저장하고 ESP를 4byte증가 시킨다. POP명령어시 현재 가리키는 ESP의 값을 꺼내고 ESP를 4byte감소 시킨다.(PUSH, POP, CALL, RET 등의 명령어들은 ESP를 직접 조작한다.)

세그먼트 레지스터

CS (Code Segment) : 명령어 코드들이 저장되어 있는 부분을 코드 세그먼트라고 하며 CS레지스터는 이곳의 시작 주소를 가지고 있다. CS주소에 명령어 포인터(Instruction pointer,EIP)레지스터의 오프셋 값을 더하면, 실행하기 위해 메모리로부터 가져와야할 명령어 주소가 된다.

DS(Data Segment) : 주로 전역, 정적(static)변수 데이터가 들어있는 데이터 세그먼트의 시작 위치를 가리키는 레지스터이다. 명령어들은 DS를 사용하여 데이터의 위치를 알아낸다.

SS(Stack Segment) : 프로그램은 주소, 데이터의 임시저장을 위해 스택을 사용한다. 스택 세그먼트의 시작 주소를 SS에 저장한다. SS에 스택 포인터(ESP)레지스터의 오프셋 값을 더하면 실제 메모리 주소가 나온다.

ES(Extra(Data) Segment) : 일반적으로 문자열 연산에서 사용된다. 이 경우 EDI레지스터와 연관된다.

FS : 유저모드에서 FS레지스터는 TEB(Thread Environment Block, 현재 실행중인 스레드에 대한 정보를 저장하고 있는 구조체)을 지칭한다. 커널 모드에서는 일반적으로 KPCR(Kernel Process Control Region)을 가리킨다.

GS : 여분의 데이터 세그먼트로 주로 스택 스매싱이 일어났는지 확인할 때 사용한다.

Flag Register

Carry Flag(CF) : 부호없는 산술 연산 수행결과로 자리 올림이나 내림이 발생할 때 set(1) 된다. 어셈블리어 STC, CLC, CMC 명령어를 이용하여 직접적인 플래그 값 수정이 가능하다.

Parity Flag(PF) : 연산 결과의 bit중 1인 bit의 개수가 짝수개이면 1, 홀수개이면 0으로 세팅된다.

Auxiliary Carry Flag(AF) : 보조 캐리플래그이다. 산술연산 8비트연산자에서 비트 3에서 비트4로 캐리가 발생할 경우 1로 set된다.

Zero Flag(ZF) : 산술 연산 또는 논리 연산의 결과가 0이되면 플래그 값이 1로 set된다. 결과가 0이 아니라면 플래그 값은 0으로 리셋된다. 두값의 산술연산이나 루프 내부의 카운터를 점차적으로 빼서 0을 만들어 플래그를 Set시켜 루프를 빠져나가는 등 여러방식으로 사용된다.

Sign Flag(SF) : 최상위 bit(MSB)의 결과가 같은 값으로 저장된다. SF=1일 경우 음수이고, SF = 0일 경우 양수이다.

Overflow Flag(OF) : 부호 있는 산술연산의 결과가 sign-bit(MSB)를 제외한 최대 허용 정수값보다 크거나 최소 정수값보다 작으면 1로 Set 된다.

제어플래그

Direction Flag(DF) : 문자열 데이터 복사에서 방향을 결정하는 Flag이다. set(1)되어있으면 높은 주소 -> 낮은 주소로 Clear(0)으로 되어있으면 낮은 주소 -> 높은 주소로 처리한다. 어셈블리어 STD로 set, CLD로 Clear 가능하다.

시스템 플래그

Trap Flag(TF) : 플래그가 0일때 CPU는 평소처럼 명령어를 실행시킨다. 플래그가 1일 때에는 CPU가 하나의 명령을 시행하고 Interrupt가 발생한다. Interrupt가 발생하면 디버거가 해당 프로세스를 attach할 수 있는 상태가 된다.

Interrupt Flag(IF) : 프로세스에 인터럽트가 발생했을 때 인터럽트처리를 할것인지 제어한다. 플래그 값이 1로 Set 되어있으면 외부로부터 인터럽트 신호가 들어왔을 때 인터럽트를 처리하고, 0으로 Clear되어있으면 인터럽트 신호가 들어오더라도 반응하지 않는다.

명령어 지시자 레지스터

EIP(Extended Instruction Pointer) : 다음에 실행할 명령어 들어 이는 메모리 주소를 가리킨다. CS세그먼트 레지스터를 참조하여 실행번지를 참조한다. CPU는 EIP의 주소를 보고, 다음에 처리할 명령어를 가져온다. 직접적인 조작이 불가능 하다. 그러나 call, jmp, loop, interrupt와 같은 프로그램 흐름제어 명령을 통해 EIP를 자동으로 변경할 수 있다.

배열을 이용한 리스트의 구현

리스트의 이해

리스트라는 자료구조는 구현방법에 따라서 크게 두가지로 나뉜다.

- 순차 리스트 : 배열을 기반으로 구현된 리스트

- 연결 리스트 : 메모리의 동적 할당을 기반으로 구현된 리스트

리스트 자료구조의 기본적이고 중요한 특성

- 리스트 자료구조는 데이터를 나란히 저장한다. 그리고 중복된 데이터의 저장을 막지 않는다.

리스트 자료구조의 ADT

void ListInit(List * plist);

-초기화 할 리스트의 주소 값을 인자로 전달한다.

-리스트 생성 후 제일 먼저 호출되어야 하는 함수이다.

void LInsert(List * plist, LData data);

-리스트에 데이터를 저장한다. 매개 변수 data에 전달된 값을 저장한다.

int LFirst(List * plist, LData * data);

-첫번째 데이터가 pdata가 가리키는 메모리에 저장된다.

-데이터의 참조를 위한 초기화가 진행된다.

-참조 성공시 TRUE(1), 실패시 FALSE(0) 반환

int LNext(List * plist, LData * pdata);

-참조된 데이터의

LData LRemove(List * plist);

-LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제한다.

-삭제된 데이터는 반환된다.

-마지막 반환 데이터를 삭제하므로 연이은 반복 호출을 허용하지 않는다. 

함수들에 대한 소스코드이다. list를 사용하기 위해서는 변수 들의 초기화에 해당하는 ListInit 함수를 호출해야한다. 이후 LInsert 함수를 통해 list에 데이터를 삽입 시킬 수가 있다.

데이터 참조에 사용되는 함수는 LFirst와 LNext이다. LNext가 호출되기 위해서는 반드시  LFirst가 호출되어야 한다. 이후 LNext를 호출하여 list를 순차적으로 참조할 수있다. LNext함수는 호출 할 때마다 다음에 저장된 데이터를 얻을 수 있다.

데이터 삭제에는 LRemove함수가 사용된다. LFrist나 LNext함수를 통해 참조된 데이터를 삭제하는데 사용된다.

LCount함수는 리스트에 저장되어있는 데이터의 수를 반환한다.

List를 이용한 문제 03-1

List를 이용한 문제 03-2

추상 자료형(Abstract Data Type)

구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것을 추상자료형 또는 간단히 ADT라 한다.

특수한 자료형을 정의하고 이 자료형을 기반으로 하는 연산의 종류를 결정하는 것도 자료형 정의의 일부로 보아야 한다. 자료형과 연산의 종류가 결정되었을 때 자료형의 정의는 완성된다.

위에서 말하는 연산의 의미는 +, -와 같은 C언어에서 제공하는 연산을 의미하는 것이 아니고, 정의한 자료형을 기반으로 제공할 수 있는 기능 관련 연산을 의미하는 것이다. 즉, '자료형'의 정의에 '기능' 혹은 '연산'과 관련된 내용을 명시 할 수 있다는 것이다.

ex)

wallet 자료형의 구조체 정의

typedef struct _wallet

{

     int   coin100Num;

     int   bill5000Num;

}Wallet;

Wallet의  ADT

int TakeOutMoney(Wallet * pw, int coinNum, int billNum)

-첫번째 인자로 전달된 주소의 지갑에서 돈을 꺼낸다.

-두번째 인자로 꺼낼 동전의 수, 세번째 인자로 꺼낼 지폐의 수를 전달한다.

- 꺼내고자 하는 돈의 총액이 반환된다. 그리고 그만큼 돈은 차감된다.

void PutMoney(Wallet * pw, int coinNum, int billNum)

-첫번째 인자로 전달된 주소의 지갑에 돈을 넣는다.

-두번째 인자로 넣을 동전의 수, 세번째 인자로 넣을 지폐의 수를 전달한다.

- 넣은 만큼 동전과 지폐의 수가 증가한다.

wallet자료형의 정의에 '기능' 혹은 '연산'을 하는 TakeOutMoney 함수와 PutMoney함수가 ADT에 포함된다. 

하노이 타워 문제의 이해

하노이 타워 : 원반은 한번에 하나씩 옮길 수 있으며 옮기는 과정에서 작은원반위에 큰 원반이 올라가서는 안된다.

원반의 수가 많아질수록 하노이 타워의 문제해결이 어려워진다. 그러나 하노이 타워도 원반의 수가 늘어날 수록 일련의 과정을 더 많이 반복할 뿐이다.

하노이 타워 문제의 해결

막대 A,B,C가 있을 때, 막대 A에 꽂혀있는 원반 n개를 막대 C로 옮기는 과정은 다음과 같이 재귀적으로 구성이 된다.

1.작은 원반 n-1개를(가장 큰 맨 아래 원반을 제외한 나머지 원반)A에서 B로 이동

2.큰 원반(맨 아래의 원반) 1개를 A에서 C로 이동

3.작은 원반(가장 큰 원반 제외) n-1개를 B에서 C로 이동.

위를 재귀로 구성할 때 탈출 조건은 "이동해야할 원반의 수가 1개"인 경우이다. 이동해야할 원반의 수가 1개이면 그냥 옮기면 되기 때문이다.

하노이 타워 함수

위 함수의 매개변수 from에 꽂혀있는 num개의 원반을 by를 거쳐서 to로 이동한다는 의미의 변수들이다.

HanoiTowerMove(num-1, from, to, by);

위 함수는 n-1개의 원반을 A에서 B로 이동하는 함수이다. 이후 printf()함수를 통해 가장 큰 원반(맨 아래의 원반)1개를 A에서 C로 이동한다.

HanoiTowerMove(num-1, by, from, to);함수를 통해 B에 있는 n-1개의 원반을 C로 이동시킨다.

재귀함수 : 함수 내에서 자기 자신을 다시 호출하는 함수

ex)

void Recursive(void)

{

    printf("Recursive call! \n");

    Recursive();

}

Recursive 함수내의 Recursive 함수가 호출되면, Recursive 함수의 복사본이 만들어져서 복사본이 실행되는 구조로 재귀함수를 진행한다.

함수를 구성하는 명령문은 CPU로 이동이 되어서(복사가 되어서)실행이 된다. 그런데 이 명령문은 얼마든지 CPU로 이동이(복사가) 가능하다. 즉 Recursive함수의 중간까지 명령문을 실행하다가 다시 Recursive함수의 앞부분에 위치한 명령문을 CPU로 이동시키는 것은 문제가 되지 않는다.

또한 위 코드처럼 재귀함수를 정의하는데 있어서 탈출조건을 구성하는 것은 매우 중요한일이다.

재귀의 활용

피보나치 수열 : Fibonacci Sequence

피보나치 수열은 재귀적인 형태를 띄는 대표적인 수열로서 앞엣것 두개를 더해서 현재의 수를 만들어가는 수열이다. 첫번째, 두번째 값은 0,1로 고정이고 세번째부터 앞의 두수를 더하여 수열을 만들어간다.

피보나치 수열 수학적 표현

위 수식의 코드

int Fibo(int n)

{

     if(n == 1)

         return 0;

     else if(n== 2)

         return 1;

     else

        return Fibo(n-1)+Fib(n-2);

}

위 코드의 함수 호출 순서를 정리하기 위한 코드

return Fibo(n-1)+Fibo(n-2); //return Fibo(6)+Fibo(5);

에서 +연산자 왼편의 Fibo 함수 호출이 완료되어야 +연산자 오른편에 있는 Fibo함수 호출이 진행된다.

위 순서대로 재귀함수들이 실행된다 즉 return Fibo(n-1)+Fibo(n-2); //return Fibo(6)+Fibo(5);

에서 +연산자 왼편의 Fibo 함수 호출이 완료되어야 +연산자 오른편에 있는 Fibo함수 호출이 진행된다.

이진 탐색(Binary Search) 알고리즘 소개

이진 탐색 알고리즘은 정렬된 데이터가 아니면 적용이 불가능하다. 이진 탐색 알고리즘은 탐색의 대상을 반복해서 반씩 떨구어내 탐색 대상을 찾아내는 알고리즘 이다.

정렬된 배열에서 탐색의 시작 위치를 first, 탐색의 마지막 위치에 해당하는 인덱스 값을 last로 표기한다. 이진 탐색 알고리즘이 진행되면 first와 last는 점차 가까워진다.

이진 탐색은 first가 last보다 큰경우 종료된다. 이렇게 종료되는 경우는 탐색에 실패한 경우이다.

if(target < ar[mid])

     last = mid -1;

else

     first = mid + 1;

이진 탐색 알고리즘에서 위처럼 구성해야 하는 이유는 한번 탐색한 대상을 포함하지 않기 위함과 탐색의 대상이 배열에 존재하지 않는 경우를 위함이다.

if(target < ar[mid])

    last = mid;

else

    first = mid;

위처럼 알고리즘이 구성되어 있을 때, 탐색의 대상이 배열에 존재하지 않는다면 프로그램은 끝나지 않을것이다. 탐색의 대상이 존재하지 않을때 이진 탐색을 끝내는 경우는 first가 last보다 커졌을 때 이기 때문이다.

이진 탐색 알고리즘의 시간 복잡도 계산(worst case 기준)

이진 탐색 알고리즘에서 데이터 수가 n개일 때, 최악의 경우 비교연산 횟수는 얼마인가?

n일때 1회

데이터 개수가 n/2일때 1회

데이터 개수가 n/4일때 1회

데이터 개수가 n/8일때 1회

....

개수가 1일때 1회이다.

위 과정을 정리하면 n이 1이 될때까지 2로 나눈 횟수 k회, 이진 탐색에서 비교연산 k회를 진행,

데이터가 1개 남았을 때 비교연산 1회

즉 최악의 경우에 대한 시간복잡도 함수 T(n)은 T(n) = K+1 이 된다.

n이 1이 되기까지 2로 나눈 횟수가 k이다.

n과 k에 관한식

-> n x (1/2)^k = 1

위 식을 정리하면

n x (1/2)^k =1 -> n x 2^(-k) = 1 -> n = 2^k

(^는 제곱이다.)

n = 2^k에서 양변에 log2를 취해준다.

log2 n = klog2 2 -> log2 n = k

위 식은 이진 탐색 알고리즘의 worst case 시간 복잡도 함수이다. 즉 T(n) = log2 n이 된다.

정확하게는 T(n) = log2 n +1이지만 +1은 중요하지 않다.

n이 증가함에 따라 연산횟수가 로그적으로 증가한다는 것이 중요하다.

위처럼 식(T(n))을 구성함으로써 데이터 수의 중가에 따른 연산횟수의 변화 정도를 판단할 수 있게 된다.

빅-오 표기법(Big-Oh Notation)

빅-오 : 시간복잡도 함수 T(n)에서 가장 영향력이 큰부분

T(n) = n^2 + 2n + 1

위 식에서 n이 커짐에 따라 2n + 1이 미치는 영향은 미미해지므로 T(n) = n^2으로 간략화 할 수 있다.

이를 빅-오 표기법으로 표현하면 O(n^2)이며, 읽을 때는 "빅-오 오브 n^2(Big-Oh of n^2)"이라고 읽는다.

단순하게 빅-오 구하기.

T(n)이 다항식으로 표현된 경우, 최고차항의 차수가 빅-오가 된다.

ex)

T(n) = n^2 + 2n + 9               ->      O(n^2)

T(n) = n^4 + n^3 + n^2 + 1    ->      O(n^4)

T(n) = 5n^3 + 3n^2 + 2n + 1   ->      O(n^3)

위를 일반화 하면 다음과 같다.

T(n) = a(m)n^m + a(m-1)n^(m-1) + ... a(1)n^1 + a(0)     -> O(n^m)

시간 복잡도 함수가 n^2인 경우에도, 9999n^2인 경우에도 O(n^2)이다. 빅-오는 '데이터 수의 증가에 따른 연산횟수의 증가 형태(패턴)'을 나타내는 표기법 이기 때문이다.

O(log n)의 경우 데이터 수 증가에 따라 로그 그래프와 유사한 형태를 띤다.

대표적인 빅-오

1.O(1)

상수형 빅-오 이다. 데이터 수와 상관없이 연산횟수가 고정인 알고리즘이다. 데이터 수와 상관없이 3회 진행되는 알고리즘일지라도 O(1)이 된다. O(1)는 연산횟수가 고정인 알고리즘이라는 의미가 담겨있다.

2.O(log n)

로그형 빅-오 이다. '데이터 수의 증가율'에 비해서 '연산횟수의 증가율'이 훨씬 낮은 알고리즘을 의미한다. 매우 바람직한 유형이다. 로그의 밑이 얼마냐에 따라서 차이가 나긴 하지만 알고리즘 성능 관점에서는 매우 미미하기 때문에 대부분의 경우 무시된다.

3.O(n)

선형 빅-오 이다. 데이터 수와 연산횟수가 비례하는 알고리즘 이다.

4.O(nlog n)

선형로그형 빅-오 이다. 이는 데이터의 수가 두배로 늘 때, 연산횟수는 두배를 조금 넘게 증가하는 알고리즘을 의미한다.

5.O(n^2)

데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘을 의미한다. 데이터양이 많은 경우 부적절하다. 이중으로 중첩된 박복문 내에서 연산이 진행되는 경우 발생한다.

6.O(n^3)

데이터 수의 세제곱에 해당하는 연산 횟수를 요구하는 알고리즘이다. 이는 삼중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우에 발생한다.

7.O(2^n)

지수형 빅-오 이다. '지수적 증가'라는 무서운 연산횟수의 증가를 보인다. 이러한 성능을 보이는 알고리즘이라면 개선의 과정을 거쳐서 현실적인 알고리즘으로 수정해야 한다.

빅-오 성능 대소관계

O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(n^3) < O(2^n)

순차 탐색 알고리즘과 이진 탐색 알고리즘 비교

순차 탐색 알고리즘 : T(n) = n

이진 탐색 알고리즘 : T(n) = log2 n + 1

각각의 빅-오

순차 탐색 알고리즘 : O(n)

이진 탐색 알고리즘 : O(log2 n)

O(n)의 경우 실험을 하지 않아도 비교연산 횟수와 데이터 수가 같음을 알 수 있다.

이진 탐색 알고리즘 실험 코드

위 실행결과를 통해 순차탐색 알고리즘과 이진 탐색 알고리즘 연산 횟수 비교

                     n                           순차 탐색 연산횟수                             이진 탐색 연산횟수

                    500                                 500                                                   9

                   5000                               5000                                                  13 

                  50000                              50000                                                 16

위 결과를 통해 O(n)과 O(log n) 알고리즘의 연산횟수에 얼마나 큰 차이가 있는지 알 수 있다.