Flexible　optimization　on　video　coding　computational　complexity　is　imperative　to　adapt　to　diverse　terminals　in　video　streaming,　especially　with　high　definition　videos　and　increasingly　comprehensive　encoders.　Until　now,　few　efforts　have　been　contributed　to　the　encoder　of　multiview　videos,　which　complicates　its　encoding　structure　with　duplex　frame　display.　To　address　this　issue,　we　propose　a　flexible　complexity　optimization　framework　in　this　paper.　In　the　first　place,　the　proposed　algorithm　flexibly　reduces　the　encoder　complexity　at　different　external-defined　complexity　constraints;　furthermore,　it　is　also　committed　to　compression　efficiency　optimization　at　different　complexity　levels.　The　framework　is　achieved　by　a　hybrid　approach:　complexity　allocation,　which　allocates　the　external-defined　complexity　constraint　to　all　views,　hierarchical　layers　and　frames　based　on　linear　programming;　and　complexity　regulation,　which　dynamically　adjusts　local　candidate　partitions　to　fulfil　the　targeted　local　complexity　constraint,　with　a　probability-driven　Alternate　Partition　Cost　(APC)　minimization.　The　overall　algorithm　is　implemented　on　the　popular　multiview　encoder,　Multiview　High　Efficiency　Video　Coding　(MV-HEVC),　with　promising　Rate-Distortion　(RD)　performances　at　different　complexity　constraints,　which　are　also　superior　to　two　recent　complexity　optimization　algorithms.　©　1991-2012　IEEE.