함수
.clear() :리스트 초기화
x in iterableObject (T/F) :iterable object 안에 x존재 진위 여부
뮤터블 이뮤터블
자료 구조
- 데이터를 저장하고 정리하는데 사용 될 수 있는 장소
ex)array,tree
알고리즘
- 어떤 문제를 해결하기 위한 절차의 집합 -> 이들이 computer science를 만든다
자료구조 알고리즘 배우는 이유
- 코드를 작성하는데 시간을 줄이고 메모리 사용을 효율적이게 사용하기 위해
재귀함수
-
함수 내에서 자기 자신을 다시 호출하는 것
-
스택내에 쌓아 두었다가 일괄로 처리
-
반복문으로 치환 가능 시간 복잡도에 따라서 사용하기 좋을경우도 있고 아닐 경우도 존재, 반복문 이 더 빠르지만 재귀를 사용하면 보기 더 쉽고 직관적임(유지 보수 좋음)
-
문제의 정의 부분 잘 알아야함(선언적 프로그래밍), 종료 조건 설정
선언적 프로그래밍 : 목표를 명시하고 알고리즘을 명시하지 않는것 알고리즘은 컴퓨터가 알아서 찾는다
시간 복잡도
-
함수에서 실행이 되어 결과물 까지 나오는 시간, 얼마나 빠르게 결과를 출력하는가
-
시간 복잡도에서 상수는 큰 의미가 없음 (n -> 무한대 경우 10000n < n^2 )
-
알고리즘의 수행 시간을 좌우하는 기준은 for loop 반복 횟수, 특정한 행이 수행되는 횟수,함수의 호출 횟수...
공간 복잡도
- 메모리를 얼마나 사용하는가
점근적 표기(입력의 크기가 충분히 큰 경우에 대한 분석)
-
big-O표기법( O((g(n)) )
worst-case의 경우의 성능을 판단하여 평균과 가까운 성능으로 예측,
기껏해야 g(n)의 비율로 증가하는 함수 ,
f(n) = O((g(n)) : f는 g보다 크게 증가하지 않는다,
data(n)가 증가할수록 얼마나 코드가 느려지냐, -
알 수 있는 한 최대한 tigth하게
복잡도가 nlogn + 5n = O(nlogn)인데 굳이 O(n^2)으로 쓸 필요없다.#### 결론: 점근적 표기법은 성장률에 가장 중요한 부분을 제외하고 계수와 상수처럼 중요하지 않은부분 제외시키는 것
Big-O notation
- O(n) : data(n)의 값이 커지면 비례하여 시간이 걸림 ex)길이가 n인 배열을 특정값과 비교하기
int addUp(int n){
int sum =0;
for(int i = 0; i<=n ; i++){
sum += i;
}
return sum;- O(1) : n의 크기와 상관없이 항상 일정한 시간 걸림
int addUp(int n){
int sum = n *(n+1) / 2;
return sum;
}- O(logn) :n이 커져도 실행시간이 느리게 증가, 이진 탐색처럼 탐색량을 반으로 줄이기에 데이터가 크더라도 로그 시간에 비례
def logarithmic_function(n):
result = 1
while result < n:
result *= 2
return result
n = 16
result = logarithmic_function(n)
print(f"The result is {result}")
O(nlogn): 대표적으로 병합 정렬 배열을 반으로 나누고 각각 정렬하기에 nlogn
O(n^2) : 2차원 배열
c
#include <stdio.h>
int main(){
for(i=0;i<n;i++){
for(j=0;i<n;j++)
}
} #시간 복잡도 n^2