설정된 시간이 지난 후 기능을 중지하고 다음 함수로 이동

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의 배열에서 실행되고 조각을 다시 결합하기 위해 일정량의 작업을 수행합니다. + O (1)

이 점화식은 O (2 ^{n으로 해결한다 - 이것은 우리}

T (N) ≤ 2T (1 N)으로 알고리즘의 런타임을 표현할 수 있다는 것을 의미), 입력 크기에 지수 적입니다. 몇 가지 입력에 걸리는 시간을 측정하면 기하 급수적 인 증가 곡선을보고 있음을 알면서 외부에서 추정 할 수 있어야합니다. 특히 추가 된 모든 요소는 런타임을 두 배로 늘립니다. 거기에서 2 ⁿ, 1 분 및 알고리즘의 런타임을 알려진 입력 크기로 설정하고 거기에서 물건을 가져 오는 방정식을 설정하면됩니다.