python - 搜索从某个前缀开始的列表元素的函数的 O(n) 难度是多少？

Question

我写了下面的代码，代码是要找到list中以某个前缀开头的所有元素，面试官问代码的O()难度是多少，我回答O(n)，其中n是元素的数量在列表中，在我看来这是错误的答案，因为招聘人员非常失望。正确答案是什么？为什么？

def count_elemets(list_elements, prefix):
    result = []
    for i in list_elements:
        if i.startswith(prefix):
            result.append(i)
    return result

正确答案是什么，为什么？

Answer 1

我查看了 startswith 函数的实现。

有几点需要考虑。首先，for 循环是 O(n) 和匹配字符的数量(假设为 k)，使得复杂度为 O(k*n)(仍然可以认为是 O(n))。

另一点是，startswith 函数似乎可以将 tuple 作为前缀参数，如果元组中存在任何前缀(startswith 那前缀)，则返回 True。因此，也有人可能会争辩说前缀元组的大小也是相关的。

不过，这些都可以考虑O(n)，我不知道你的面试官是否要求更具体的答案，但我认为他应该更好地解释答案中到底对你有什么要求。

如果你想看一看，这里是实现。

static PyObject *
unicode_startswith(PyObject *self,
                   PyObject *args)
{
    PyObject *subobj;
    PyObject *substring;
    Py_ssize_t start = 0;
    Py_ssize_t end = PY_SSIZE_T_MAX;
    int result;

    if (!stringlib_parse_args_finds("startswith", args, &subobj, &start, &end))
        return NULL;
    if (PyTuple_Check(subobj)) {
        Py_ssize_t i;
        for (i = 0; i < PyTuple_GET_SIZE(subobj); i++) {
            substring = PyTuple_GET_ITEM(subobj, i);
            if (!PyUnicode_Check(substring)) {
                PyErr_Format(PyExc_TypeError,
                             "tuple for startswith must only contain str, "
                             "not %.100s",
                             Py_TYPE(substring)->tp_name);
                return NULL;
            }
            result = tailmatch(self, substring, start, end, -1);
            if (result == -1)
                return NULL;
            if (result) {
                Py_RETURN_TRUE;
            }
        }
        /* nothing matched */
        Py_RETURN_FALSE;
    }
    if (!PyUnicode_Check(subobj)) {
        PyErr_Format(PyExc_TypeError,
                     "startswith first arg must be str or "
                     "a tuple of str, not %.100s", Py_TYPE(subobj)->tp_name);
        return NULL;
    }
    result = tailmatch(self, subobj, start, end, -1);
    if (result == -1)
        return NULL;
    return PyBool_FromLong(result);
}

https://github.com/python/cpython/blob/master/Objects/unicodeobject.c