1. 알고리즘 표기법

알고리즘 표기법을 통해서 알고리즘이 얼마나 잘 설계되었고
코드가 얼마나 잘 구현되었는지 알 수 있다.

알고리즘의 효율성을 나타내는 척도인것이다.
알고리즘 표기법에는 2가지가 있다.

• 실행시간 : 프로그램이나 알고리즘이 동작하는데 걸리는 시간

1) Big - O

알고리즘을 수행하는데 필요한 시간의 상한선

2) Ω(Omega)

알고리즘을 수행한는데 필요한 시간의 하한선

컴퓨터 과학자는 최악의 경우 또는 평균적으로 동작하는 것에 관심이 많으므로
Big - O와 상한선에 더 신경을 쓴다.

2. 선형 검색

1) 문자열의 비교

문자열의 비교는 숫자처럼 "=="을 이용할 수 없다.
문자열은 자체가 배열이므로 배열 내부의 문자를 하나씩 비교해야하기 때문이다.

이는 string.h에 있는 함수를 사용하면 쉽게 가능한데

# include<string.h>
# include<cs50.h>
# include<stdio.h>

int main(void){
	string names[4] = {"AB","BC","CD","DE"}; // 배열의 정적 초기화
    for (int i=0;i<4;i++) {
    	if(strcmp(names[i],"AB")==0) {
        	printf("Found\n");
            return 0;
        }
    }
    return 1;
}

strcmp는 문자열이 동일한 경우 0을 반환한다.

2) 전화번호부

# include<string.h>
# include<cs50.h>
# include<stdio.h>

int main(void){
	string names[4] = {"AB","BC","CD","DE"}; // 배열의 정적 초기화
    string numbers[4] = {"01","12","23","34"};
    
    for (int i=0;i<4;i++) {
    	if(strcmp(names[i],"AB")==0) {
        	printf("%s\n",numbers[i]);
            return 0;
        }
    }
    return 1;
}

이렇게 코드를 만들면 "AB"의 번호를 출력할 수 있다.

하지만 이 코드는 names 와 numbers의 인덱스로 연결되어있어
만약 names를 정렬을 하거나 이름만을 추가하는 등 번호와 이름의 순서가 달라지면 번호를 찾는 것이 불가능하다.

이를 보완하기 위해서 코드를 수정할 수 있다.

names,numbers를 함께 저장하는 우리만의 자료형을 만들어서 해결하는 것이다.

# include<string.h>
# include<cs50.h>
# include<stdio.h>

typedef struct
{
	string name;
    string number;
}
person; // person이라는 자료형을 만듦

int main(void){
	
    person people[4];
    
	people[0].name = "AB"; 
    people[0].number = "01";
    
    people[1].name = "BC"; 
    people[1].number = "12";
    
    people[2].name = "CD"; 
    people[2].number = "23";
    
    people[3].name = "DE"; 
    people[3].number = "34";
    
    
    
    for (int i=0;i<4;i++) {
    	if(strcmp(people[i].name,"AB")==0) {
        	printf("%s\n",people[i].number);
            return 0;
        }
    }
    return 1;
}

struct는 여러가지 자료형을 위한 그릇이다.
이처럼 정보를 묶어서 만들 수 있다.