内置python函数的时间/空间复杂度

问题描述：

split/strip/open(内置python函数)的时间/空间复杂度是多少?

What is the time/space complexity of split/strip/open (in-built python functions)?

有人知道我可以在哪里查询这些功能的时间/空间复杂性吗?

Does anyone know where i can look up on the time/space complexity of these functions?

答

确切的答案取决于将哪些属性输入到函数中.最简单的查找方法可能是检查这些功能的源代码.可在此处找到python源代码.

The exact answer will depend on what properties are fed into the function. The easiest way to find out would probably be to examine the source code for those functions. The python source code can be found here.

让我们看看 split的来源.代码根据属性运行不同的循环.这是按空格分割的循环.

Lets take a look at the source for split. The code runs different loops depending on the properties. This is the loop for splitting by whitespace.

    while (maxcount-- > 0) {
    while (i < str_len && STRINGLIB_ISSPACE(str[i]))
        i++;
    if (i == str_len) break;
    j = i; i++;
    while (i < str_len && !STRINGLIB_ISSPACE(str[i]))
        i++;

在此代码中，该函数将查看字符串中的每个字符(除非达到了最大计数).对于大小为n的字符串，最里面的循环将运行n次.时间复杂度为 O(n)

In this code, the function will look at each character in the string (unless the maxcount is reached). The inner most loops will run n times for a string of size n. Time complexity is O(n)

地带来源逐步浏览字符串.

    i = 0;
if (striptype != RIGHTSTRIP) {
    while (i < len) {
        Py_UCS4 ch = PyUnicode_READ(kind, data, i);
        if (!BLOOM(sepmask, ch))
            break;
        if (PyUnicode_FindChar(sepobj, ch, 0, seplen, 1) < 0)
            break;
        i++;
    }
}

j = len;
if (striptype != LEFTSTRIP) {
    j--;
    while (j >= i) {
        Py_UCS4 ch = PyUnicode_READ(kind, data, j);
        if (!BLOOM(sepmask, ch))
            break;
        if (PyUnicode_FindChar(sepobj, ch, 0, seplen, 1) < 0)
            break;
        j--;
    }

    j++;
}

这使剥离的时间复杂度为 O(n).

This gives strip a time complexity of O(n).

open()的源没有循环.这就是我们所期望的.没有什么可以循环的.

The Source for open() shows no loops. This is what we would expect. There is nothing to loop through.

内置python函数的时间/空间复杂度

相关推荐