此方法如何在Big O表示法中执行？

Question

下面的方法"getValue"解析一个String,根据String构建一个Map并返回一个与该键相关的值.以下方法的性能是"getValue"O(n)的平方吗？

我基于此,因为每次添加新的键值字符串时,都需要对其进行解析,然后将该项添加到Map中.

import java.util.Arrays;
import java.util.List;
import java.util.Map;

public class MeasureBigO {

    private static final String testString = "keyTest=keyValue";

    public static void main(String args[]){

        System.out.println(getValue("keyTest"));

    }

    private static String getValue(String key){

        Map<String, String> config = new java.util.HashMap<String, String>();
        List<String> configItems = Arrays.asList(testString.split(","));

        for (String configItem : configItems) {
            configItem = configItem.trim();
            List<String> keyValuesPairs = Arrays.asList(configItem.split("="));

            try {
                config.put(keyValuesPairs.get(0).trim(), keyValuesPairs.get(1).trim());
            }
            catch(IndexOutOfBoundsException ioobe){
                return null;
            }
        }

        return config.get(key);

    }

}

Answer 1

该算法的复杂性在于O(n)其中n的项目数量configItems.

• 我基于以下格式testString:它可以及时拆分O(1).
• 环路与周围configItems成正比O(n).
• 其他split操作configItem也是O(1)如此.

除了他们之外,你在你的循环指令,以便在实践中C * O(n)哪里C是他们的一些成本不变.