Table lookup will win hands down in terms of cycle count, since calculating note frequencies involves several very costly mathematical operations.
Expanding the table to 512 bytes will help squeeze a few more cycles, if needed. Generally the idea is to split low and high bytes of the lookup values, and align each table to a 256 byte border, so you can directly translate the indices, like so
ld h,table_base_lo_bytes>>8
ld l,a ; set index
ld c,(hl) ; load lo-byte
ld h,table_base_hi_bytes>>8 ; or just inc h if hi-byte lut follows on next page
ld b,(hl) ; load hi-byte, frequency divider now in BC
