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

Question

我写了下面的代码，代码应该在列表中找到以某个前缀开头的所有元素，面试官问代码有什么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作为前缀参数，如果元组中存在任何前缀(以该前缀开头(，则返回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