在设定的时间量后停止功能并转到下一个功能

Question

我试图测试一些算法，并计时它们，如果它们花费太长时间（准确地说60秒），我想停止它们。我已经试着摆弄时钟功能，但我似乎无法让它停下来，并转向下一个测试。我想这样做而不编辑isUnique函数本身。有没有办法通过从开始计时操作并在经过60秒后停止操作？以下是节目至今..

#include "stdafx.h" 
#include <iostream> 
#include <vector> 
#include <ctime> 
#include <chrono> 
#include <cstdlib> 
#include <random> 
#include <algorithm> 

using namespace std; 

bool isUnique(const vector<int>& arr, int start, int end) { 
    if (start >= end) return true; 
    if (!isUnique(arr, start, end - 1)) 
     return false; 
    if (!isUnique(arr, start + 1, end)) 
     return false; 
    return (arr[start] != arr[end]); 
} 

bool isUniqueLoop(const vector<int>& arr, int start, int end) { 
    if (start >= end) return true; 
    for (int i = start; i < end; i++) 
     for (int j = i + 1; j <= end; j++) 
      if (arr[i] == arr[j])return false; 
    return true; 
} 

bool isUniqueSort(const vector<int>& arr, int start, int end) { 
    if (start <= end) return true; 
    vector<int> buf(arr); 
    sort(buf.begin() + start, buf.begin() + end); 
    for (int i = start; i < end; i++) 
     if (buf[i] == buf[i + 1]) return false; 
    return true; 
} 

int main() { 

    int max = 0; 
    cout << "Enter a number for the Max range: "; 
    cin >> max; 
    default_random_engine randGen(time(0)); 
    uniform_int_distribution<int> randNum(0, max); 
    int i; 
    int j; 
    int n = randNum(randGen); 
    int m = n; 
    double timeout = 60.0; 

    vector<int> myVect; 

    for (i = 0; i <= m; i++) { 
     myVect.push_back(randNum(randGen)); 
     //cout << myVect[i] << endl; 
    } 
    cout << "Recursive Algorithm Test... " << endl; 
    cout << endl; 

    // recursive algorithm 
    clock_t start = clock(); 
    isUnique(myVect, 0, m); 
    if (isUnique(myVect, 0, m) == true) { 
     cout << "The Vector is Unique! " << endl; 
    } 
    else { 
     cout << "The Vector is not Unique! " << endl; 
    } 
    clock_t end = clock(); 
    double time = (double)(end - start)/CLOCKS_PER_SEC * 1000.0; 
    cout << "CPU Time used for this algorithm: " << time << " ms" << endl; 

    if (time > 60000) { 
    cout << "This function takes too long! " << endl; 
      } 

    cout << "------------------------------------" << endl; 


    cout << "Iterative Algorithm Test... " << endl; 
    cout << endl; 
    // iterative algorithm 
    clock_t start2 = clock(); 
    isUniqueLoop(myVect, 0, n); 
    if (isUniqueLoop(myVect, 0, n) == true) { 
     cout << "The Vector is Unique! " << endl; 
    } 
    else { 
     cout << "The Vector is not Unique! " << endl; 
    } 
    clock_t end2 = clock(); 
    double time2 = (double)(end2 - start2)/CLOCKS_PER_SEC * 1000.0; 
    cout << "CPU time used for this algorithm: " << time2 << " ms. " << endl; 
    if (time2 > 60000) { 
     cout << "This function takes too long! " << endl; 
    } 
    cout << "------------------------------------" << endl; 


    cout << "Sort Algorithm Test... " << endl; 
    cout << endl; 
    // sort algorithm 
    clock_t start3 = clock(); 
    isUniqueSort(myVect, 0, n); 
    if (isUniqueSort(myVect, 0, n) == true) { 
     cout << "The Vector is Unique! " << endl; 
    } 
    else { 
     cout << "The Vector is not Unique " << endl; 
    } 
    clock_t end3 = clock(); 
    double time3 = (double)(end3 - start3)/CLOCKS_PER_SEC * 1000.0; 
    cout << "CPU time used for this algorithm: " << time3 << " ms. " << endl; 
    if (time3 > 60000) { 
     cout << "This function takes too long! " << endl; 
    } 
    cout << endl; 
    system("pause"); 
    return 0; 

第一isUnique设置（）函数总是需要很长的，因为它的无效和递归，这很好，它应该是这样的。但是，我不知道如何终止这个特定的功能，并且如果它需要很长时间才能转到下一个功能。对罗嗦的帖子感到抱歉。有什么建议么？

Answer 1

让我们假设你在一个大小为n的输入数组上运行这个算法。你的算法触发两个递归调用，每个调用都运行在一个大小为n-1的数组上，然后进行持续的工作以将这些碎片重新组合在一起。这意味着，我们可以表达你的算法的运行时间为

T（n）的≤ 2T（N - 1）+ O（1）

这种递推关系解决到O（2 ^ñ），指数大小的输入。如果您测量一些输入需要多长时间，那么您应该能够从那里向外推断，知道您正在寻找指数增长曲线。具体而言，每个添加的元素将使运行时间加倍从那里开始，你只需要建立一个包含2 ⁿ的公式，一分钟，以及算法在某些已知输入大小上的运行时间，并从那里获取信息。