Zeitkomplexität einer Lösung zu einer Codility-Demo-Aufgabe

Dobi

Hallo zusammen,

ich beschäftige mich gerade mit folgender Aufgabe:
http://codility.com/demo/take-sample-test/ndi/

Given an array A of N integers, we draw N discs in a 2D plane such that the I-th disc is centered on (0,I) and has a radius of A[I]. We say that the J-th disc and K-th disc intersect if J ? K and J-th and K-th discs have at least one common point.

Write a function:

class Solution { public int number_of_disc_intersections(int[] A); }

that, given an array A describing N discs as explained above, returns the number of pairs of intersecting discs. For example, given N=6 and:

A[0] = 1 A[1] = 5 A[2] = 2
A[3] = 1 A[4] = 4 A[5] = 0

intersecting discs appear in eleven pairs of elements:

0 and 1,
0 and 2,
0 and 4,
1 and 2,
1 and 3,
1 and 4,
1 and 5,
2 and 3,
2 and 4,
3 and 4,
4 and 5.

so the function should return 11.

The function should return -1 if the number of intersecting pairs exceeds 10,000,000.

Assume that:

N is an integer within the range [0..10,000,000];
each element of array A is an integer within the range [-2,147,483,648..2,147,483,647].

Complexity:

expected worst-case time complexity is O(N*log(N));
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Folgende Lösung hat anscheinend eine time complexity von O(N * log(N))

int number_of_disc_intersections ( const vector<int> &A ) {
	typedef vector<int> V;
	V starts(A.size(), 0);
	V ends(A.size(), 0);
	for (V::size_type i(0); i < A.size(); ++i)
	{
		if (static_cast<int>(i) < A[i])
			++starts.front();
		else
			++starts[i - A[i]];
		if (i+A[i] >= A.size())
			++ends.back();
		else
			++ends[i + A[i]];
	}
	int active=0;
	int result(0);
	for (V::size_type i(0); i < A.size(); ++i)
	{
		result += active * starts[i] + (starts[i] * (starts[i] - 1)) / 2;
		if (result > 10000000)
			return -1;
		active += starts[i]-ends[i];
	}
	return result;
}

Wo kommt das *log(N) her? Ich seh nur O(N). Es finden doch nur 2*N Schleifendurchläufe statt.

Gruß
Dobi