A complexity based joint rate-distortion optimization algorithm is presented, which taking the complexity factor of video coding into account based on the rate-distortion optimization algorithm in H.264/AVC video coding standard.Thus a better effect can be obtained on the tradeoff between rate-distortion performance and video coding complexity.Besides that, this framework introduces a complexity control factor to control the extent of complexity.Tests show that the proposed framework can reduce the complexity without much sacrifice in coding efficiency.