假设一个具有 Base 类型的继承层次结构具有 F 个虚函数、D 个不同的派生类型,并假设每个派生类型覆盖所有虚函数。
为 Base* 类型的指针 p 调用虚函数之一的时间复杂度是多少?
此外,如果总共有 O 个对象(在类型之间平均分配)并且所有对象都具有相同的数据成员,系统的空间复杂度是多少?
最佳答案
调用函数的时间复杂度为 O(1)。每个类都有一个“vtable”,它本质上是一个函数指针结构 - 每个对象都有一个指向这个 vtable 的指针,因此调用虚函数只是在 vtable 中查找函数指针并调用它。
O 个对象的空间完整性是 O(O),因为它与对象的数量成线性关系。
关于c++ - C++中调用虚函数的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23502600/