java - 这个带有 for 循环的递归调用的 Big-O 时间复杂度是多少

Question

问题，在分析下面代码的时间复杂度时(先不管空间复杂度)。这会是 O(n) 吗？递归调用计数为常量？我不确定，因为 for 循环中的递归调用。

public void printViews(View view) {
        if (view instanceof ViewGroup && ((ViewGroup)view).getChildCount() > 0) {

            ViewGroup viewGroup = ((ViewGroup)view);
            int childCount = viewGroup.getChildCount();

            for (int i = 0; i < childCount; i++) {
                Log.d("Test", viewGroup.getChildAt(i).getClass().getSimpleName());

                if (viewGroup.getChildAt(i) instanceof ViewGroup)
                    printViews(viewGroup.getChildAt(i));  //recursion
            }
        } else {
            Log.d("Test", view.getClass().getSimpleName());
        }
    }

Answer 1

它是 O(n)。

你做的是 View 树上的DFS。递归调用不是常量，但它是一种遍历树的方式。

查看链接了解更多详情: https://en.wikipedia.org/wiki/Depth-first_search