1. 최대 하위 시퀀스와 문제

입력 예: 4 - 35 - 2 6 - 2 출력: 11

1.1 이분법 귀속 구해 - 시간 복잡도: O(NlogN)

int getMax3 (int a, int b, int c)
{
    int max = a;
    if (max < b)
        max = b;
    if (max < c)
        max = c;
    return max;
}
int getMaxSum(const vector &arr, int bgn, int end)
{
    if (bgn >= end)
        return 0;
    int mid = (bgn + end) / 2;
    int leftMaxSum = getMaxSum(arr, bgn, mid);
    
    // mid + 1， 
    int rightMaxSum = getMaxSum(arr, mid + 1, end);
    
    int leftMaxBorder = 0, leftTmp = 0;
    for (int i = mid; i >= bgn; --i)
    {
        leftTmp += arr[i];
        if (leftTmp > leftMaxBorder)
            leftMaxBorder = leftTmp;
    //    if (leftTmp < 0)    // ， 
    //        break;
    }
    int rightMaxBorder = 0, rightTmp = 0;
    for (int i = mid + 1; i < end; ++i)
    {
        rightTmp += arr[i];
        if (rightTmp > rightMaxBorder)
            rightMaxBorder = rightTmp;
    //    if (rightTmp < 0)
    //        break;
    }
    return getMax3(leftMaxSum, rightMaxSum, leftMaxBorder + rightMaxBorder);
}

1.2 한 번에 풀기 - 시간 복잡도: O(N)

int getMaxSubSum(const vector &arr, int bgn, int end)
{
    int maxSum = 0;
    int sumTmp = 0;
    for (int i = bgn; i < end; ++i)
    {
        sumTmp += arr[i];
        if (sumTmp > maxSum)
            maxSum = sumTmp;
        else if (sum < 0)
            sumTmp = 0;
    }
    return maxSum;
}

2. 알고리즘 시간 복잡도가 O(logN)인 일반적인 문제:

2.1 대분 찾기(binary search) - 시간 복잡도: (<=log2N)

int binSearch(const vector &arr, int bgn, int end, int target)  //end- 
{
    int ret = -1;
    while (bgn < end)
    {
        int mid = (bgn + end) / 2;
        if (target == arr[mid])
        {
            ret = mid;
            break;
        }
        else if (target > arr[mid])
            bgn = mid + 1;
        else    
            end = mid;
    }
    return ret;
}

2.2 두 정수 최대 공약수 구해(유클리드 알고리즘) - 시간 복잡도: (<= 2logN)

unsigned int getGCD(unsigned int m, unsigned int n)
{
    while (n > 0)
    {
        int rem = m % n;
        m = n;
        n = rem;
    }
    return m;
}

여기는 사실 귀속의 사상을 운용했다. m와 n의 최대 공인자는 n과rem(m%n)의 최대 공인자이다.그러면 n과rem의 최대 공인자가 m와 n의 최대 공인자라는 것만 설명하면 이 귀속을 진행할 수 있다.그래서 문제는 n과rem의 최대 공인자가 왜 m와 n의 최대 공인자입니까?
사고방식: m>n을 가정하고 mn이 있다. m와 n의 최대 공인자는 A이고 m=xA, n=yA이다.rem=m%n->m-zn(z=m/n),rem=0, n은 양자의 최대 공인자이다.rem>0,rem=xA-zyA,rem%A=0->m와 n의 최대 공인자는 n과rem의 최대 공인자로 이와 같이 추정된다

2.3멱 연산 - 시간 복잡도: (<= 2logN)

long long pow(long long x, unsigned int n)
{
    if (0 == n)
        return 1;
    if (n % 2)
        return pow( x*x, n/2 ) * x;
    else
        return pow( x*x, n/2 );
}

2^15를 입력으로 하면 2log(15) = 6차 곱셈 연산이 2^16을 입력으로 하면 4+1(<2log(16)=8) 곱셈 연산만 필요하고, 코드를 수정하여 출구판단(if(1==n)을 추가하여 4차례 곱셈 연산으로 만들 수도 있지만, 매번 파워에 들어갈 때마다 한 번 더 판단해야 한다
　　PS: 1. 책에서 2^62를 예로 들면 모두 9차례의 곱셈 연산이 필요하지만 추론 알고리즘 과정은 개인적으로 문제가 있다고 생각한다.실제 과정은 우선 파워 입구 매개 변수 x*x의 값을 n==0까지 층층이 연산해야 한다.그리고 알고리즘이 연산이 끝날 때까지 역순으로 층층이 pow*x의 값을 계산한다.코드 중 문장 pow(x*x, n/2)는 pow(x, n/2)*pow(x, n/2)로 대체할 수 있지만 효율은 매우 낮을 것이다. 왜냐하면 대량의 중복성 작업을 진행했기 때문이다

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

데이터 구조와 알고리즘 분석(1)