Within the framework of generalized combinatorial approaches, complexity is determined as a disorder measure for hierarchical statistical ensembles related to Cayley trees possessing arbitrary branching and number of levels. With strengthening hierarchical coupling, the complexity is shown to increase monotonically to the limit value that grows with tree branching. In contrast to the temperature dependence of thermodynamic entropy, the complexity is reduced by the variance of hierarchical statistical ensemble if the branching exponent does not exceed the gold mean. Time dependencies are found for both the probability distribution over ensemble states and the related complexity. The latter is found explicitly for self-similar ensemble and ...