Алгоритм для поиска наиболее эффективного способа отправки данных по отдельности

Question

Есть 2 компьютера A и B. Компьютер A может отправлять данные с x Мбайт/с и компьютером B в y MB/s.
Пример - Если x = 20, y = 10 и Z = 100, то минимальное время будет составлять 4 секунды, поскольку компьютер A может отправлять данные 80 МБ за 4 секунды, а B может отправлять 20 МБ за 2 секунды параллельно.
Алгоритм, приведенный ниже, имеет временную сложность O (n^2). Как мы можем решить это более эффективно?

EDIT - Как это может быть сделано для русских компьютеров и найти данные, переданные с каждого компьютера?

Мое решение -

int main() 
{ 
    int x = 50; 
    int y = 10; 
    int Z = 200; 

    vector<int> xvec, yvec; 
    for(int i = x;i <= Z; i+= x) 
    { 
     xvec.push_back(i); 
    } 

    for(int i = y;i <= Z; i+= y) 
    { 
     yvec.push_back(i); 
    } 

    for(int i = 0; i < xvec.size(); i++) 
    { 
     for(int j = 0; j < yvec.size(); j++) 
     { 
      if(xvec[i] + yvec[i] >= Z) 
      { 
       cout << "min time : " << i+1; 
       exit(0); 
      } 
     } 
    } 
} 

Answer 1

Если вопрос действительно вычислить его для этих двух узлов, то комментарии на ваш вопрос в порядке. Если вопрос заключался в вычислении для произвольного количества узлов, то ваша проблема является экземпляром проблемы потока в графах. Итак, закодируйте свою проблему на графике и используйте для нее известный стандартный алгоритм, например, Ford-Fulkerson O (| V | * | E | u_ {max}), Эдмунд Карп O (| V | | E |^2), или Dinic O (| V |^2 * | E |). После того, как вы нашли максимальный поток, вы можете разделить количество данных на макс. течь.

Answer 2

Как это сделать для n компьютеров?

Логика z/(x1+x2+...+xn) - это самый эффективный и простой способ понять логику.

Использование функции ceil обеспечит, что у вас есть избыточная часть для многих вычислений, например 50 МБ и 3 компьютера со скоростями 5 МБ, 4 МБ и 2 МБ в секунду. После расчета ваше возможное минимальное время - 50/(5+4+2)=4.54, и система будет ждать еще одну секунду через 4 секунды, чтобы обрабатывать часть 0.54 s (будет решать, какой компьютер выполнить - возможно, самый быстрый).