Lesson 12: MinMaxDivision (Min Max Division)

Lesson 12: MinMaxDivision
https://codility.com/programmers/lessons/12

単純なバイナリ・サーチの問題です。

#include <alloca.h>

int check(int num, int K, int* A, int N)
{
    int i = 0;
    
    int sum = 0;
    while (i < N){    
        //indeed, we don't need below because the lower limit is max(A).
        if (A[i] > num){
            return 0;
        }
        sum += A[i];
        if (sum > num){
            sum = A[i];

            K--;
            if (K == 0){
                return 0;
            }
        }
        i++;
    }
    
    return 1;
}

int solution(int K, int M, int A[], int N) 
{
    int max = A[0];
    int sum = 0;
    
    int i;
    for (i = 0; i < N; i++){
        max = max < A[i] ? A[i] : max;
        sum += A[i];
    }
    
    int beg = max;
    int end = sum; 
    
    int min = sum; 
    while (beg <= end){
        int mid = (beg + end) / 2;
        if (check(mid, K, A, N)){
            min = mid;
            end = mid - 1;
        }
        else {
            beg = mid + 1;
        }
    }
    
    return min;

}

追記：この問題はO(N * log(N + M))の計算量を求めています。上のコードをもっと単純にして、ありうる範囲のすべてを探索することを考えると（上のコードのように範囲をmax(A)とsum(A)で狭めないと）バイナリ・サーチの範囲が0からN * Mになりますから、O(N * log(N * M))の計算量になりますよね。

で、これで問題の言うO(N * log(N + M))になってると考えていいんだろうかと悩んでいたところ、下記のサイトで説明がありました。
http://blog.csdn.net/caopengcs/article/details/41834173

まず log(N * M) = log N + log Mですので
O(log(N * M)) = O(log N + log M)
と言えますね。

ここで log N + log M は 2 * log(max(N, M))より以下になるので
 O(log N + log M) <= O(2 * log(max(N, M)))
と言えますね。

ここでmax(M, N)はN + Mより小さいので、
O(2 * log(max(N, M))) <　O(2 * log(N + M))
といえます

ビッグ・オー表記からは定数を消してしまって良いので、O(log(N + M))という形がえられ、これが今回のバイナリ・サーチの部分の計算量として言ってしまえるようですね。