Какой алгоритм нахождения минимального числа лучше

Question

Какой алгоритм нахождения минимального числа лучше

username Знаток (478), закрыт 10 месяцев назад

 static int min1(std::vector _vec) { 
    typename std::vector::iterator last = _vec.end(); 
    for (typename std::vector::iterator first = _vec.begin(), twofirst = ++_vec.begin() + 1; twofirst != last; ++twofirst) { 
        if (*first > *(twofirst)) { 
            std::swap(*first, *twofirst); 
        } 
        else { 
            continue; 
        } 
    } 
    return *_vec.begin(); 
} 
//--------------------------------------------------------------------------
static int min2(std::vector _vec) { 
    typename std::vector::iterator last = _vec.end(); 
    int i = *(_vec.begin()); 
    for (typename std::vector::iterator first = _vec.begin(); first != last; ++first) { 
        if (i > *first) { 
            i = *first; 
        } 
    } 
    return i; 
}

Дополнен 11 месяцев назад

суть первого алгоритма - найти минимальное число без вспомогательной переменной, перетаскивая минимальное значение каждый раз в начало вектора если оно меньше первого элемента вектора
суть второго думаю все знают

Answer 1

Андрей Высший разум (472599) 11 месяцев назад

 static int min3(std::vector &_vec) {
  int min = _vec[0];
  for(int v: _vec) {
    if (v < min) { min = v; }
  }
  return min;
}

Второй вариант, но без бессмысленного усложнения кода вручную созданным итератором.

Обмен местами двух значений требует трёх операций копирования. Что намного медленнее, чем единственная операция копирования в классическом способе.

ПапаВысший разум (148350) 11 месяцев назад

retunr!!!

Андрей Высший разум (472599) Папа, Спасибо.

usernameЗнаток (478) 11 месяцев назад

почему требует копирования если есть конструктор перемещения?

Андрей Высший разум (472599) Максим Уразов, А что такое, по твоему, перемещение? Просто подумай, как именно перемещение работает на уровне команд процессора, в котором никакого "перемещения" не существует, а есть только копирование. Перемещение объекта - это копирование указателя для объект. И эффективно оно, когда объект существенно больше указателя и копировать указатель получается намного быстрее, чем побайтно копировать весь объект. Но целое число НЕ БОЛЬШЕ указателя. И копирование целого числа происходит не медленнее, чем копирование указателя.

Answer 2

Данил Ласый Просветленный (44174) 11 месяцев назад

Не-а. Ищи дальше

Answer 3

Второй алгоритм (`min2`) является более предпочтительным способом для нахождения минимального числа в векторе по нескольким причинам:

1. **Эффективность:** Второй алгоритм проходит по вектору один раз и сравнивает каждый элемент с текущим минимальным значением, сохраненным в переменной `i`. Это делает его более эффективным по сравнению с первым алгоритмом, который переставляет элементы внутри вектора, что потенциально может привести к большему числу операций.

2. **Простота и понятность:** Второй алгоритм легче понять, так как он следует классическому подходу поиска минимального элемента в коллекции: итерация по элементам и сравнение их с текущим минимумом.

3. **Неизменяемость исходных данных:** Первый алгоритм модифицирует исходный вектор, перемещая минимальный элемент в начало вектора. Во многих случаях предпочтительнее сохранять исходные данные без изменений, что делает второй алгоритм более универсальным и безопасным в использовании.

4. **Скорость выполнения:** Перестановка элементов в векторе, особенно в больших векторах, может быть довольно затратной по времени операцией. Второй алгоритм избегает этих дополнительных затрат, ограничиваясь только чтением элементов.

Таким образом, второй алгоритм (`min2`) предпочтительнее для нахождения минимального числа в векторе из-за его эффективности, простоты и сохранения исходных данных без изменений.

Answer 4

Оба алгоритма имеют одну и ту же сложность по времени O(n), где n - количество элементов в векторе. Однако второй алгоритм (min2) является более эффективным и простым.

Второй алгоритм (min2) использует только одну переменную для хранения текущего минимального значения. Он проходит по всем элементам вектора и сравнивает их с текущим минимальным значением. Если находит меньшее значение, то обновляет переменную с минимальным значением.

Первый алгоритм (min1) использует обмены элементов вектора для перетаскивания минимального элемента в начало вектора. Хотя этот подход может быть корректным, он менее эффективен, так как требует дополнительных операций обмена элементов.

Таким образом, для нахождения минимального числа вектора предпочтительнее использовать второй алгоритм (min2), так как он является более простым и эффективным.