Wahl der Datenstruktur II

CONST free = 0; queen = 1; TYPE Piece = SHORTINT; (* free or queen *) TYPE Position = SHORTINT; (* [0..n-1] *) TYPE Board = RECORD nofqueens: SHORTINT; size: SHORTINT; piece: ARRAY maxn, maxn OF Piece; END; PROCEDURE Threatened(board: Board; row, col: Position) : BOOLEAN; (* check if a queen may be set at (row,col) without being in conflict with formerly set pieces *) VAR r, c: Position; BEGIN (* check row *) c := 0; WHILE c < board.size DO IF board.piece[row, c] # free THEN RETURN FALSE END; INC(c); END; (* check column and both diagonals *) (* ... *) RETURN TRUE END Threatened;

Wenn als Datenstruktur ein 2-dimensionales Feld entsprechend dem Schachbrett verwendet wird, werden die Überprüfungen sehr aufwendig.

4 Schleifen jeweils mit n Schritten führen zu einem Aufwand von O(n).

	Wenn als Datenstruktur ein 2-dimensionales Feld entsprechend dem Schachbrett verwendet wird, werden die Überprüfungen sehr aufwendig.
	4 Schleifen jeweils mit n Schritten führen zu einem Aufwand von O(n).