대 O 표현법
2872 단어 데이터 구조
1. 정수 n 단계 곱 하기
int fact(int n)
{
if(n<=1) return 1;
else return n*fact(n-1);
}
？O（n）
n fact（n）
：
2. 계산
T（n）=1，n=1；2T(n/2)+n，n>1
n
： n=2^k, ，
일반 법칙
1. for 순환: 기껏해야 이 for 순환 내 문장의 운행 시간 입 니 다.×반복 횟수 끼 워 넣 기 for 동 리 ~
2. 순서 문 구 는 각 문장의 실행 시간 을 T1 (N) + T2 (N) = max (O (f (N), O (g (N))) 로 구 합 니 다 (최대 값 을 선택 하 십시오).
3. if / else 운행 시간 이 판단 과 조건문 보다 긴 사람
로그 상황
만약 에 하나의 알고리즘 이 상수 시간 O1 로 문제 의 크기 를 일부분 (보통 1 / 2) 으로 줄 이면 이 알고리즘 은 O (log N) 의 - eg. 분할 알고리즘 으로 나 누 어 찾 습 니 다. 유클리드 알고리즘 이 상수 시간 O1 로 문제 의 크기 를 상수 로 줄 이면 O (N)
총결산
O (1) O (1) 는 이 알고리즘 의 실행 시간 (또는 실행 시 사용 공간) 이 항상 상수 임 을 나타 내 며 입력 한 데이터 세트 가 크 든 작 든 상관없다.
O (N) O (N) 는 입력 데이터 의 크기 에 따라 선형 으로 변 하 는 알고리즘 의 성능 을 나타 낸다.
O (N ^ 2) O (N ^ 2) 는 하나의 알고리즘 의 성능 이 입력 데이터 의 증가 에 따라 2 차 성장 을 나타 낸다 는 것 을 나타 낸다. 가장 흔히 볼 수 있 는 알고리즘 은 입력 데 이 터 를 끼 워 넣 는 순환 이다.
O (2 ^ N) O (2 ^ N) 는 하나의 알고리즘 의 성능 이 입력 데이터 의 매번 증가 에 따라 두 배 증가 할 것 임 을 나타 낸다. O (2 ^ N) 의 성장 곡선 은 폭발 적 인 성장 곡선 으로 시작 할 때 부 드 럽 지만 데이터 가 증가 한 후 곡선 이 매우 가 파 르 게 증가한다. 전형 적 인 O (2 ^ N) 방법 은 배 파 나 수열 의 재 귀 계산 이 이 루어 지 는 것 이다.
O (nlog2n) 선형 대수 급: 빠 른 정렬 O (nlog2n) 는 하나의 알고리즘 의 성능 이 입력 데이터 의 크기 에 따라 선형 대수 급 으로 변화 한 다 는 것 을 나타 낸다.
O (log N) 분할 알고리즘, 대 분 검색, 유클리드 알고리즘
(flag: 저녁 보충)
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
