Methods, apparatus, systems and articles of manufacture are disclosed to measure compliance of a virtual computing environment. An example method disclosed herein includes determining, with a processor, a maximum surprisal value of a policy to be enforced on a computing resource in a computing environment, the maximum surprisal value corresponding to a probability of the computing resource being in-compliance with the policy without testing the computing resource with respect to the policy, determining a current surprisal value of the computing resource with respect to the policy based on knowledge of at least one condition of policy being at least one of satisfied by or inapplicable to the computing resource, and determining a compliance score of the computing resource with respect to the policy based on the maximum surprisal value of the policy and the current surprisal value of the computing resource with respect to the policy.