コーディングテスト合格者になる Python版-7期

시간복잡도-개념

빅오 표기법은 실제 실행 시간을 정확하게 나타내는 것이 아니라, 입력 크기 n이 커질 때 연산량이 어떤 비율로 증가하는지를 나타내는 표기법이다. 실제 실행 시간은 상수 계수, 컴퓨터 성능, 프로그래밍 언어, 구현 방식 등에 따라 달라질 수 있다. 예를 들어 다음 두 알고리즘이 있다고 가정할 수 있다. 알고리즘 A: 2n²번 연산 알고리즘 B: 100n번 연산 입력 크기 n이 작을 때는 알고리즘 A가 더 빠를 수 있다. 예를 들어 n = 10일 때는 다음과 같다. 알고리즘 A: 2 × 10² = 200 알고리즘 B: 100 × 10 = 1,000 이 경우 시간 복잡도가 O(n²)인 알고리즘 A가 O(n)인 알고리즘 B보다 실제 연산 횟수가 적다. 하지만 n이 계속 커지면 상황이 달라진다. n²은 n보다 훨씬 빠른 속도로 증가하기 때문에 충분히 큰 입력에서는 O(n²)

박종희 · 시간 복잡도- 개념

拍手 0 · コメント 1

시간복잡도 - 코드 분석

시간 복잡도는 입력의 크기, 즉 리스트 numbers의 길이(원소의 개수)를 n이라고 가정하고 n에 대한 함수로 분석해야 합니다. def find_max(numbers): max_num = numbers[0] for num in numbers: if num > max_num: max_num = num return max_num 배열 안의 요소에 대해 비교하는 연산을 한 번씩 배열의 길이만큼 실행하기 때문에 시간복잡도는 O(n)이다. 문제 2아래 Python 코드의 시간 복잡도를 빅오(Big-O) 표기법으로 표현하고, 왜 그렇게 생각하는지 근거를 서술하세요. 시간 복잡도는 입력의 크기, 즉 리스트 numbers의 길이(원소의 개수)를 n이라고 가정하고 n에 대한 함수로 분석해야 합

임승화 · 시간복잡도 - 코드 분석

拍手 0 · コメント 1

시간 복잡도 - 개념 미션 제출!

O(n²)라고 해서 항상 느린 것은 아닙니다. 입력이 작을 때는 상수나 구현 방식에 따라 더 빠를 수도 있습니다. 하지만 입력이 커질수록 실행 시간이 얼마나 빨리 증가하는지(성장률)를 비교할 수 있기 때문에, 빅오 표기법은 알고리즘의 효율성을 판단하는 기준으로 사용됩니다. 문제 2입력이 매우 커지면 상수와 낮은 차수의 항의 영향은 거의 없어지고, 가장 높은 차수의 항이 실행 시간을 결정합니다. 따라서 3n² + 10n + 5는 n²의 영향이 가장 크므로 O(n²)로 표현합니다. 문제 3O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(2ⁿ) O(1) : 배열 인덱스로 원소 접근 O(log n) : 이진 탐색(Binary Search) O(n) : 리스트 전체 순회 O(n log n) : 병합 정렬(Merge Sort), 퀵 정렬(평균) O(n²) : 이중 반복문, 버블 정렬 O(2ⁿ) : 모든 부분집합 탐색(Brute Force)

Chan · 시간 복잡도- 개념

拍手 0 · コメント 1