GUI布局计算是否必然存在指数级时间复杂度？

框架设计背景 #

我正在设计一个包含widget和layout的简易GUI框架，以基础水平布局为例：子widget横向排列，剩余空间留空，纵向拉伸至布局全高。

widget的尺寸无法提前完全确定：水平布局会要求子widget取最小横向空间；而填充应用窗口的根布局尺寸已知，若水平布局为根布局，则子widget高度可知。

布局函数接口设计 #

为此我设计了布局函数接口：

Dimensions layout(Dimensions minDimensions, Dimensions maxDimensions);

水平布局中首个子widget的调用方式为：

child->layout(Dimensions(0, parentMinDimensions.height), parentMaxDimensions);

因为其宽度可任意小但不超过布局总宽度，纵向需匹配布局约束。

水平布局的初始实现与问题 #

尝试实现水平布局的layout函数：

Dimensions layout(Dimensions minDimensions, Dimensions maxDimensions) {
    int remainingWidth = maxDimensions.width;
    for (Widget *child : children) {
        Dimensions childDimensions = child->layout(
            Dimensions(0,              minDimensions.height),
            Dimensions(remainingWidth, maxDimensions.height)
        );
        remainingWidth -= childDimensions.width;
        minDimensions.height = max(minDimensions.height, childDimensions.height);
    }
    return Dimensions(maxDimensions.width-remainingWidth, minDimensions.height);
}

但存在问题：若水平布局是垂直布局的子布局，输入的最小与最大高度不同，子widget可能出现高度不一致。这似乎需要两次遍历子widget：

Dimensions layout(Dimensions minDimensions, Dimensions maxDimensions) {
    // First pass - determine height
    int height = minDimensions.height;
    int remainingWidth = maxDimensions.width;
    for (Widget *child : children) {
        Dimensions childDimensions = child->layout(
            Dimensions(0,              minDimensions.height),
            Dimensions(remainingWidth, maxDimensions.height)
        );
        remainingWidth -= childDimensions.width;
        height = max(height, childDimensions.height);
    }
    // Second pass - apply height
    remainingWidth = maxDimensions.width;
    for (Widget *child : children) {
        Dimensions childDimensions = child->layout(
            Dimensions(0,              height),
            Dimensions(remainingWidth, height)
        );
        remainingWidth -= childDimensions.width;
    }
    return Dimensions(maxDimensions.width-remainingWidth, height);
}

布局以任意大小和深度的树状层级组织，节点多次遍历子树会导致指数级复杂度，这在窗口resize等需实时重布局场景中表现糟糕。

核心疑问 #

常见GUI框架是否存在此问题？是实际层级不够深未显影响，还是存在能保证最坏情况优于指数级复杂度且不损失布局灵活性的策略？

已知方案的局限性 #

我知道可拆分出两个函数：

Dimensions measure(Dimensions minDimensions, Dimensions maxDimensions);
void layout(Dimensions exactDimensions);

虽measure可保证单次遍历树，但仍需为每个子widget调用两者，指数级复杂度仍存在；且无法在最小与最大高度相等时跳过第二轮，并非全场景有益。

我也了解缓存中间结果有帮助，但是否存在能彻底改变所有场景最坏情况复杂度的策略？我关注的是大O指数级复杂度，而非常数因子优化。

内容的提问来源于stack exchange，提问作者Detheroc