알고리즘
-
알고리즘의 복잡도알고리즘/이론정리 2021. 9. 8. 18:31
시간 복잡도 문제의 크기와 이를 해결하는 데 걸리는 시간 사이의 관계 공간 복잡도 문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계 평균 시간 복잡도 임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균 최악 시간 복잡도 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간 빅오 notation 점근 표기법의 하나 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현 (알고리즘의 복잡도를 표현할 때 흔히 쓰임) o(logn): 입력의 크기의 로그에 비례하는 시간 소요 o(n) : 입력의 크기에 비례하는 시간 소요 계수는 그다지 중요하지 않음 선형시간 알고리즘 - o(n) 예 : n개의 무작위로 나열된 수에서 최댓값을 찾기위해 선형탐색 알고리즘을 적용 최댓값 - 끝까지 다 살펴보기 전까지..
-
-
-
선형 배열알고리즘 2021. 9. 8. 17:33
선형 배열 (Linear Arrays) : 리스트 활용 Python 리스트에 활용할 수 있는 연산들 1. 리스트 길이와 관계 없이 빠르게 실행 결과를 보게되는 연산들 원소 덧붙이기 .append() 원소 하나를 꺼내기 .pop() 위 연산들은 리스트의 길이와 무관하게 빠르게 실행할 수 있는 연산들이다. 리스트의 길이가 아무리 길어도 맨 끝에 요소 하나를 추가하는 것이나 맨 끝 요소 하나를 빼는건 빠르게 할 수 있는 일이다. --->o(1) 2. 반면 , 리스트의 길이에 비례해서 실행 시간이 걸리는 연산들 원소 삽입하기 .insert() 원소 삭제하기 .del() 이런 연산들은 리스트의 길이가 길면 길수록 처리가 오래 걸리게 된다. 구체적으로 말하면 리스트의 길이예 실행 시간이 비례한다. 리스트 길이가 1..