Постоянное амортизированное время
Функция scanf автоматически удаляет пробелы, прежде чем пытаться проанализировать другие вещи, кроме символов. %c, %n, %[] являются исключениями, которые не удаляют ведущие пробелы. gets читает новую строку, оставленную предыдущим scanf. Поймайте новую строку, используя getchar();
scanf("%d", &a);
getchar(); // catches the newline character omitted by scanf("%d")
gets(b);
3 ответа
Амортизируемое время объяснено простыми словами:
, Если Вы, операция говорит миллион раз, Вы действительно не заботитесь о худшем случае или лучшем случае той операции - о чем Вы заботитесь, то, сколько времени потрачено всего при повторении операции миллион раз.
, Таким образом, не имеет значения, если операция является очень медленной время от времени, пока "время от времени", достаточно редко для замедления быть растворенным далеко. По существу амортизируемое время означает "среднее время, потраченное на операцию, если Вы делаете много операций". Амортизируемое время не должно быть постоянным; у Вас может быть линейное и логарифмическое амортизируемое время или безотносительно.
Позволяют нам взять пример циновок динамического массива, к которому Вы неоднократно добавляете новые объекты. Обычно добавление объекта занимает время (то есть, O(1)). Но каждый раз, когда массив полон, Вы выделяете вдвое больше места, копируете Ваши данные в новый регион и освобождаете старое пространство. Принятие выделяет и освобождает выполненный в постоянное время, этот процесс расширения берет O(n) время, где n является текущим размером массива.
Так каждый раз, когда Вы увеличиваетесь, Вы берете во вдвое большее количество времени, когда последние увеличиваются. Но Вы также ожидали дважды как прежде, чем сделать его! Стоимость каждого расширения может таким образом быть "распространена" среди вставок. Это означает, что в долгосрочной перспективе, общее время, потраченное для добавления м , объекты к массиву O(m), и таким образом, амортизируемое время (т.е. время на вставку) O(1).
Это означает, что со временем, худший вариант развития событий примет значение по умолчанию к O (1), или постоянное время. Типичным примером является динамический массив. Если мы уже выделили память для новой записи, добавив, что это будет O (1). Если мы не выделили его, мы сделаем так путем выделения, скажем, дважды текущей суммы. Эта конкретная вставка будет не быть O (1), а скорее что-то еще.
то, Что важно, - то, что алгоритм гарантирует, что после последовательности операций дорогие операции будут амортизироваться и таким образом рендеринг всей операции O (1).
Или в более строгих терминах,
существует постоянный c, такой, что для каждый последовательность операций (также одно окончание дорогостоящей операцией) длины L, время не больше, чем c*L (Спасибо RafaЕ‚ Dowgird)
Производительность любой функции может быть составлена в среднем путем деления "общего количества вызовов функции" в "общее время, потраченное для всех тех выполненных вызовов". Четные функции, которые занимают больше времени и дольше у каждого вызова, который Вы делаете, могут быть составлены в среднем таким образом.
Так, сущность функции, которая работает в Constant Amortized Time, - то, что это "среднее время" достигает потолка, который не становится превышенным, в то время как число вызовов продолжает увеличиваться. Какой-то конкретный вызов может варьироваться по производительности, но за длительный период это среднее время не будет продолжать становиться больше и больше.
Это - существенная заслуга чего-то, что работает в Constant Amortized Time.