Collision detection design

[TinyTeeTree]

I have made a simple 2d shooter (bird eye view) and want your guys help on implementing the collision detection between the monsters and bullets. The problem is as follows

Each monster has locationX, locationY as coordinates.
Each monster has a Rectangle representing its collision box, (if bullet inside rectangle then its a collision).
Each bullet has locationX, locationY as coordinates as well.

pretty standard up till now.

each frame I need to check if some bullet collided with some monster.

the brutal force is to keep a list of all the bullets and monsters and to check the possibility of collision between all of them which takes O(#bullets * #monsters)

can anyone think of a clever design to achieve a better overall detection of collision?

I'm taking answers seriously, so please post well defined answers about the maintenance and memory usage that any clever trick requires

[o1vk4iN6]

Spatial partitioning is usually used such that only objects within the same area are tested against each other. Some structures are binary space partitions, quad/octree, dynamic trees that use simple shapes to divide areas based on the objects within a scene (such as AABB or spheres). AABB and spheres can be used as bounding boxes to test if two complex shapes are close enough that they could be touching before actually testing if they are touching.

[TinyTeeTree]

that's one way, I was thinking of a grid where each slot has its own list of monsters.

however, how does one maintain such a list? each iteration I have to check where all the monsters are, plus what happens when a monster gets deleted. As a problem arises in the design that now its in two different lists, or data structures. Overall its possible but still a bit troublesome, I'm getting a tingly feeling that an easier approach exists. Have you ever solved this problem efficiently xerzi?