The disclosure relates to a video encoding method and a video encoding apparatus, a computer-readable storage medium, and a computer device. The method includes: acquiring a current video frame and an initial quantization parameter; calculating first historical complexity corresponding to the current video frame at a first time granularity; acquiring a second available bit rate at a second time granularity corresponding to the current video frame and a current first available bit rate at the first time granularity corresponding to the current video frame; adjusting the second available bit rate and the first available bit rate according to complexity of the current video frame and the first historical complexity; updating the initial quantization parameter according to an adjusted second available bit rate to obtain a current quantization parameter; and encoding the current video frame according to the current quantization parameter.