In general, the best way to improve wireless connectivity is to improve the signal from the source (better antenna or higher transmit power on the router) since that will usually improve signals to all computers and other wireless devices with a single upgrade. If you just have one computer that is having problems, then an external (movable) directional antenna for that computer would be the best choice.
The cheapest way is to simply remove whatever interference is preventing you from getting a good signal in the first place. Sometimes this isn't possible (walls in the house, power lines outside, distance between devices, weak transmitters in the equipment, etc.) but if you can do it by simply changing the channel on the router, changing the location of the router, moving your 2.4Ghz cordless phone away from the router and computers (or changing its channel on the phone), you may be able to fix the problem for free..
And yes, the antenna you linked to is primarily intended to be used with a router that has a Reverse SMC connector. You'll have to check the documentation for your router (or post the exact model number here) to find out if the antenna will work for you.