为什么不考虑参数/参数传递方式的算法时间复杂度? [英] Why are not the way parameters/arguments passed considered for the time complexity of an algorithm?

问题描述

根据语言的不同，传递参数/参数的方式会具有不同的时间复杂度，这是不正确的.那么，为什么书中用来衡量时间复杂度的算法或程序中没有考虑或考虑到这一点呢?马克·艾伦·韦斯(Mark Allen Weiss)撰写的CLRS或数据结构与算法分析永远不会增加整个程序运行时传递参数的时间复杂度?我误会了吗?我知道CLRS是伪代码，但是Mark Allen Weiss的算法分析显示了Java特有的代码.

Is it not true that depending on the language that way the parameters/arguments are passed will have a different time complexity. Then why is this not factored in or considered in the algorithms or programs that books measure time complexity of? CLRS or Data Structures and Algorithm Analysis by Mark Allen Weiss never would add the time complexity of how the arguments are being passed for the total runtime of the program? Am I misunderstanding something? I know CLRS was pseudocode but the Algorithm Analysis by Mark Allen Weiss showed code specific to Java.

推荐答案

如果我正确理解了您的问题，那么您会问以下问题:

If I understand your question correctly, you're asking the following:

某些编程语言(最著名的是C和C ++)在按值传递(作为参数的副本)与按指针传递或按引用(不复制参数)之间进行区分.选择如何将参数传递给函数将改变该函数完成的工作量，因为如果按值传递，则需要复制参数.但是，CLRS根本不讨论这个问题，并且Java书籍没有解决此问题，因为它们是用Java编写的.这很重要，我们应该在意吗?

Some programming languages (most notably, C and C++) make a distinction between passing by value (making a copy of the arguments) and passing by pointer or by reference (in which the arguments aren't copied). The choice of how you pass parameters into a function changes how much work is done by the function, since if you pass by value you need to copy the arguments. However, CLRS doesn't talk about this at all, and books in Java don't address this because they're written in Java. Is this important, and should we care about it?

您正确的是，参数传递的模式绝对会影响函数运行所需的时间.例如，这不是用C ++编写的二进制搜索的很好实现:

You are correct that the mode of parameter passing absolutely makes a difference in how long the function takes to run. For example, here's a not great implementation of binary search written in C++:

/* Bad code, please don't use this. */
bool binarySearchFor(std::vector<int> values, int key) {
    std::size_t lhs = 0, rhs = values.size();

    while (lhs < rhs) {
        std::size_t mid = lhs + (rhs - lhs) / 2;
        if (values[mid] == key) return true;
        else if (values[mid] > key) lhs = mid;
        else rhs = mid + 1;
    }

    return false;
}

此函数内部的逻辑将在时间O(log n)上运行，其中n是 std :: vector 中的元素数.但是，由于向量是通过值传递的，因此简单地复制该向量将花费时间Θ(n)，这使实际算法的运行时间相形见and，并使整个过程在时间Θ(n)中运行.另一方面，更改功能以使我们可以通过 const 引用接受 values ，将运行时降低到O(log n).

The logic inside this function will run in time O(log n), where n is the number of elements in the std::vector. However, since the vector is passed by value, simply copying that vector will take time Θ(n), dwarfing the actual algorithm's runtime and making the whole thing run in time Θ(n). On the other hand, changing the function so that we accept values by const reference drops the runtime down to O(log n).

那么，为什么CLRS-或大多数其他算法书籍-都没有谈论这个?原因之一就是值传递不是所有编程语言的功能(或者至少不是以与C ++相同的方式).在Python，JavaScript，Java，LISP等中，技术上按参数通过值传递参数，但由于这些参数是引用，因此传递参数的成本始终为O(1).因此，在算法书中不讨论此问题的一个原因是，这些书谈论的是所遵循的高级概念性算法，而不是为它们提供动力的实际代码，因此并未考虑所有编程语言中的所有细节.希望您，穿着整齐又明智的读者，将他们的算法转换为您选择的编程语言，并适当利用可用的语言功能.

So, why doesn't CLRS - or most other algorithms books - talk about this? One of the reasons why is that pass-by-value isn't a feature of all programming languages (or at least, not in the same way that it is in C++). In Python, JavaScript, Java, LISP, etc., parameters are technically passed by value, but since those parameters are references, the cost of passing the parameter is always O(1). So one reason not to talk about this in an algorithms book is that those books talk about the high-level conceptual algorithms followed rather than the actual code to power them, and therefore don't account for all details found in all programming languages. It's expected that you, the Well-Dressed and Wise Reader, will translate their algorithms into your programming language of choice, making appropriate use of the available language features.

这篇关于为什么不考虑参数/参数传递方式的算法时间复杂度?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！