Форум программистов, компьютерный форум CyberForum.ru

Оптимизация времени выполнения - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Пpи помощи стека пpовести соpтиpовку http://www.cyberforum.ru/cpp-beginners/thread594746.html
Дан файл, элементами котоpого являются целые числа, упоpядоченные по возpастанию (убыванию). Пpи помощи стpуктуpы данных стек пpовести "обpатную" соpтиpовку файла по убыванию (возpастанию!)
C++ Вывести числа в порядке убывания, вычислить площадь треугольника Проверить задачу если возможно - собственно прошу вас посмотреть эту задачу. Условие: Ввести три числа. Если они могут быть длинами сторон тупоугольного треугольника, вывести их в порядке убывания, вычислить площадь полученного треугольника. Нашел подобную задачу, и в ообщем намудрил чет. #include<iostream> #include<clocale> #include <math.h> http://www.cyberforum.ru/cpp-beginners/thread594743.html
Как записать ответ с методом пузырька? C++
Собственно програмка выдает около 100 разных значений, как можно было бы записать их методом пузырька в массив? Или еще лучше, если бы, например у нас есть ответ, 2 параметра результата, например "s=100 v=10; s=30 v=12....s=55 v=33; s=33 v=11" вот отсартировать по S, что бы получилось 100 55 33 30 , а уже к ним, хоть отдельной строкой 10 33 11 12, последовтельно Можно код, пожалуйста?
Преобразование символов в числа C++
Дан текст, содержащий цифры. Вывести на экран наибольшую цифру. Помогите пожалуйста))
C++ База данных студентов (найти ошибки) http://www.cyberforum.ru/cpp-beginners/thread594688.html
доброго всем время суток!!!!хотел бы обратится за помощью к тем,кто с программированием на "ты". просьба небольшая,просто я написал прогу на С++ и хотел бы,чтобы проверили код проги на ошибки. если можно,прошу прислать уже исправленный код. тема "база данных". вот код проги. #include <stdio.h> #include <conio.h> #include <string.h> struct stud{ char fam;
Visual C++ не могли бы Вы прокомментировать программу class square { public: CPoint center; int side; void init(int side_,CPoint dot) { center.x=dot.x; center.y=dot.y; подробнее

Показать сообщение отдельно
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.06.2012, 21:35     Оптимизация времени выполнения
Цитата Сообщение от CLEO_ROCK Посмотреть сообщение
Мой код на сервере работает 1,014 с.
это не значит, что не хватает всего 0,014 с, вполне возможно что тестирующая система просто прерывает дальнейшую проверку при превышении времени выполнения уже на 0,014 с (я с таким сталкивался).
Nick Alte предложил хороший способ, но этим время сильно не выиграешь. Основная причина TL кроется здесь:
Цитата Сообщение от CLEO_ROCK Посмотреть сообщение
k (k ≤ 100 000)
Цитата Сообщение от CLEO_ROCK Посмотреть сообщение
Если xi > 0, то .... При этом 1 ≤ xi ≤ yi ≤ 100 000.
Т.е. может быть тест(ы), когда нужно около 100 000*100 000 итераций. Ни в какую секунду не влезет.
Предлагаю такой вариант:
завести еще один массив для хранения элементов типа структур. Каждый элемент такого массива будет хранить данные о диапазоне размером 1000 элементов. Т.е. элемент [0] такого массива будет хранить данные об элементах массива a[1]..a[1000]. Элемент [1] такого массива будет хранить данные об элементах массива a[1001]..a[2000]. И т.д. А хранить в каждом элементе такого массива нужно только минимальное и максимальное значение масива a[] в этом диапазоне.
Заполнение такого массива можно сделать на этапе заполнения массива a[].
Когда xi < 0, то нужно не только заменить значение в a[] но и посмотреть, не нужно ли менять значение min max в новом массиве для соответствующего диапазона.
Когда xi > 0, то искать максимальный и минимальный элемент нужно в новом массиве, и в a[] - в оставшихся кусочках, которые полностью не покрыты новым массивом.
Например xi=255, yi=6031:
- сначало минимальный и максимальный элемент ищем в новом массиве с [1] по [6] а потом ищем в массиве a[] с a[255] по a[1000] и с a[6001] по a[6031].
 
Текущее время: 01:53. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru