알고리즘 분석 - 복잡 도 잡담

알고리즘 분석
본문 기호 해석
흔히 볼 수 있 는 복잡 도 는

O (1): 상수 시간 단계

O (n): 선형 시간 단계

O (logn): 로그 시간 단계

O (n * logn): 선형 대수 시간 단계

O (n ^ k): k ≥ 2, k 차방 시간 단계

다음 책 은 본론 으로 돌아 가 허튼소리 를 시작 하 였 다.
알고리즘 분석 첫 번 째 해결 해 야 할 문제 - What to analysis
알고리즘 을 평가 하 는 중요 한 기준 은 바로 runtime 이다. runtime 에 영향 을 주 는 요소 가 매우 많다. 예 를 들 어 사용 하 는 컴 파일 러, 컴퓨터 자체 의 액세스 속도 읽 기와 쓰기 속도 등 이 있 기 때문에 반드시 다른 계량 화 된 것 이 있 고 외부 로부터 방 해 를 받 지 않 는 기준 으로 알고리즘 의 좋 고 나 쁨 을 다각도로 평가 해 야 한다.
입력 데이터 의 크기 는 main consideration 입 니 다.
두 함수 Tavg (N) Tworst (N) 를 일반 입력 조건 과 최 악의 입력 조건 으로 미리 정의 하 는 runtime
뚜렷 한 것 은 Tavg (N) ≤ Tworst (N) 가 한 조 씩 출력 할 때마다 이 두 함수 가 한 가지 더 많은 상황 에 대해 토론 해 야 합 니 다.
우리 가 일반적으로 필요 로 하 는 것 은 worst - case 의 runtime 으로 알고리즘 의 좋 고 나 쁨 을 평가 하 는 것 이다.
밤 을 들 어 달 래 요.
Given a sequence of K integers {N1,N2,...Nk}. A continuous subsequence is defined to be {Ni,Ni+1,...Nj} where 1≤i≤j≤K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.
Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.
천 서 를 먼저 번역 하 다
대 의 는 당신 에 게 서열 을 주 고 이 서열 의 가장 큰 하위 서열 과 다음 과 같은 형식 으로 결 과 를 인쇄 하 는 것 입 니 다.
최대 하위 서열 과 최대 하위 서열 중 첫 번 째 수, 최대 하위 서열 중 마지막 수
이 문 제 를 해결 하 는 알고리즘 은 여기 서 구체 적 으로 열거 하지 않 은 것 이 많다.
다음은 그것들의 복잡 도 | 알고리즘 | 1 | 2 | 3 | 4 | | | -------------------------------------------------------------------------------------------------------------| | 입력 규모 N = 10 | 0.00103 | 0.00045 | 0.00066 | 0.00034 | | | N = 100 | 0.47015 | 0.011112 | 0.00486 | 0.00063 | | | | N = 1000 | 448.77 | 1.1233 | 0.05843 | 0.00333 | | | N = 100000 | NA | 111.13 | 0.68631 | 0.03042 | N = 100000 | NA | NA | 8.0113 | 0.29832 | 이 데 이 터 는 Mingw - w64 컴 파일 러 환경 에서 측정 되 었 습 니 다.
이 문 제 는 내 가 생각 하기에 가장 좋 은 산법 문제 풀이 이다.

#include 
using namespace std;
 
int main()
{
    int N;
    cin >> N;
    int a[N];
    //        sum、           tempsum、               tempindex、            start、            end
    int sum = -1,tempsum = 0,tempindex = 0, start = 0, end = N-1;
    for(int i = 0; i < N; i++)
    {
        cin >> a[i];
        tempsum += a[i];
        if(tempsum < 0)
        {
            tempsum = 0;
            tempindex = i+1;
        }
        else if(tempsum > sum)
        {
            sum = tempsum;
            start = tempindex;
            end = i;
        }
    }
    if(sum == -1)
    {
        sum = 0;
    }
    cout << sum << " " << a[start] << " " << a[end];
    return 0;
}

runtime 의 추산
밤 을 들 어 입방 의 합 을 계산 하 다.³+2³+3³+···+n³ 가장 쉬 운 건 다 들 아 시 잖 아 요.

int Sum(int n)
{
    int i,PatialSum;
    PartialSum = 0;//**1**
    for(i=1;i<=n;i++);//**2**
        PartialSum +=i*i*i;//**3**
   return PartialSum;//**4**
}

분석 은 간단 하 다.
3. 한 번 실행 할 때마다 네 번 연산 (두 번)✖，한 번➕，또 한 번 assignment) N 회 실행, 4N 회 연산
그 중 2 곳 은 숨겨 진 시간 소모 가 있 는데 i 와 N 의 크기 관 계 를 판단 해 야 하기 때문에 모든 판단 이 복잡 도 를 N + 1 로 계산한다.
매번 i 에 대한 집행 이 증가 할 때마다 복잡 도 는 1 대 총 화 를 더 하고 복잡 도 는 N 으로 기록한다.
그러면 총 복잡 도 는 6N + 4 (함수 리 셋 무시)
그래서 우 리 는 결론 을 내 렸 다. 이 알고리즘 의 복잡 도 는 O (N) 이다.
Rules for analyze

for 순환 에 대한 복잡 도 는 O (N)

포 함 된 for 순환 에 대한 모든 for 순환 의 복잡 도 상승

연속 문

for(i=0;i

O (n) 에 이 어 O (N)²） 그러면 총 복잡 도 는 O (N).²）
1, 29 먼저 왔 습 니 다. 물고 기 를 만 지 러 가 야 합 니 다.