시간복잡도2 [자료구조] ep1+) 비트행렬로 배우는 시간복잡도의 중요성 그림과 같은 비트행렬 A가 있다고 하자, 1을 카운트하는 방법에는 다양한 방법들이 존재한다여기서 나는 2가지 방법을 얘기하려 한다 1. 가장 일반적인 방법으로 이중포문을 이용해 각 행마다 0이 나올 때까지 카운트를 하는 방법: O(n^2) 2. 제일 하단 좌측에서 시작해 우측 상단을 향해 지그재그 방식으로 올라오며 카운트를 하는 방법: O(n) 1번 방식은 시간복잡도가 O(n^2)이므로 n값이 커질수록 실행 시간은 제곱수로 증폭하게 된다반면에, 2번 방식은 시간복잡도가 O(n)이므로 n값이 커질 수록 실행 시간은 그저 선형적으로 증가하게 된다따라서 우리는 실행 시간의 측면에서 2번 방식이 압도적으로 더 좋은 것을 알 수가 있다그렇기에 우리는 상황에 맞는 자료구조와 알고리즘을 설계할 수 있는 능력을 길러야.. 2024. 4. 7. [자료구조] ep1) 자료구조 기본 지식들 ㅇ다차원 배열- 3차원 배열 - 4차원 배열 ㅇ빅오(Big O) 표기법: 연산의 횟수를 대략적(점근적)으로 표기"최악의 case 실행시간을 고려한다" [예시](1) 7n-2: O(n)(2) 3n^3 + 20n^2 + 5: O(n^3)(3) 3log(n) + log(log(n)): O(log(n))(4-1) n까지의 반복문: O(n)(4-2) n까지의 이중반복문: O(n^2)(4-3) n까지의 삼중반복문: O(n^3)(5) 조건문에서의 실행시간은 최악의 case로 합산한다+ O(log*n)은 중첩 log(n)을 의미 함수 증가율의 상한을 표시!※ 빅오메가, 빅세타 표기법과 공간복잡도는 생략 ㅇ의사코드 or 수도코드(pseudo-code): 컴퓨터가 아닌 인간에게 읽히기 위해 알고리즘을 간략하게 .. 2024. 4. 7. 이전 1 다음
