algorithm - 递归算法时间复杂度

Question

我正在尝试两个计算合并 n 个文件的递归函数的时间复杂度。

我的解决方案是 T(n)=kc+T(n-(k+1)) 其中 n> 0，T(n)= T(0) 其中 n=0。

这是正确的还是有任何其他方法可以找到时间复杂度？

这是伪代码，

//GLOBAL VARIABLES
int nRecords = 0...k; //assume there are k records
int numFiles = 0...n; //assume there are n files
String mainArray[0...nRecords]; //main array that stores the file records

void mergeFiles(numFiles) { //params numFiles
  fstream file; //file variable
  if (numFiles == 0) {
    ofstream outfile; //file output variable
    outfile.open(directory / mergedfile); // point variable to directory
    for (int i = 0; i < sizeOf(mainArray); i++) {
      oufile << mainArray[i]; // write content of mainArray to outfile
    }
    outfile.close(); //close once operation is done
  } else {
    int i = 0; //file index counter
    file.open(directory / nextfile); //open file to be read

    if (file.isOpen()) {
      while (!file.eof() && i < sizeOf(mainArray)) {
        file >> mainArray[i]; //copy contents of file to mainArray
        i++; //increase array index
      }
    }
    file.close(); //close once operation is done
    mergeFiles(numFiles - 1); //recurse function
  }
}

int main() {
  mergeFiles(numFiles); //call mergeFile function to main
}

Answer 1

按照您的公式行事。

T(n)= kc+T(n-(k+1)) = kc+kc+T(n-(k+1)-(k+1)) = kc+kc+...+T(0) = ... 
    = kc*(n/(k+1)) ~ nc = O(n).