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

Асимптотический анализ алгоритмов - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Вычислить сумму ряда с заданной точностью http://www.cyberforum.ru/cpp-beginners/thread674749.html
РЕАЛИЗАЦИЯ ИТЕРАЦИОННЫХ ЦИКЛОВ СРЕДСТВАМИ ЯЗЫКА С++ разработайте организацию выбора нужного решения с помощью переключателя switch. • с использованием цикла do....while; • с использованием цикла while; • с использованием цикла for.
C++ Двумерный массив рациональных чисел + среднее арифметическое чисел массива + сортировка методом вставки Ничего не могу понять!Вроде все правильно создавал, но считает неправильно. +Выдает ошибку Так же не могу отсортировать методом вставки элементы массива. Помогите, пожалуйста. //после завершения программы выдает ошибку: //" Stack around the variable 'mas' was corrupted. " //читал в и-нете, что вроде как я "вылез" за границы массива, но не знаю где... #include <iostream> http://www.cyberforum.ru/cpp-beginners/thread674741.html
Класс строка C++
Всем привет! Следующая проблема: Определить класс строку. В класс включить два конструктора: создание строки символов и конструктор-копия. Определить функции-члены: вывод на экран строки, перевод символов строки в нижний регистр. Может есть у кого решение?
Нахождение матрицы в матрице C++
имеем динамическую прямоугольную матрицу a(m,n), заполненная рандомом от 0 до 9. найти в этой матрице квадратную матрицу b(x,x), у которой в главной диагонали нет 0-х элементов. если их несколько, брать самую большую и самую ближнюю к A(0,0) - то есть она будет лежать выше и левее всех остальных
C++ Вывод на экран информации о человеке, номер телефона которого введен с клавиатуры http://www.cyberforum.ru/cpp-beginners/thread674724.html
Написать программу,выполняющую следующие действия: ввод с клавиатуры данных в массив,состоящий из восьми элементов типа NOTE (записи должны быть упорядочены по датам дней рождения) ;вывод на экран информации о человеке,номер телефона которого введен с клавиатуры; если такого нет, выдать на дисплей соответствующее сообщение.
C++ Описать структуру с именем NOTE Описать структуру с именем NOTE, содержащую следующие поля: фамилия,имя; номер телефона; день рождения(массив из трех чисел) подробнее

Показать сообщение отдельно
Mobalis
Сообщений: n/a
19.10.2012, 01:57     Асимптотический анализ алгоритмов
Здравствуйте. Помогите разобраться, что такое асимптотический анализ алгоритмов. Я мало что помню из школьной программы, поэтому сейчас приходится читать википедию и учить все заново, да и в программировании я новичок. Возникает много вопросов. Сейчас пытаюсь понять статью на хабре

Начну с определения:
Запись вида f(n) = O(g(n)) означает, что ф-ия f(n) возрастает медленнее чем ф-ия g(n) при с = с1 и n = N, где c1 и N могут быть сколь угодно большими числами, т.е. При c = c1 и n >= N, c*g(n) >=f(n).

1)Что такое c, c1 и N?
Читая дальше, я начал догадываться, что c и c1 это количество операций в циклах в func1() и fucn2() так ли это?

2)Как я понял,
C++
1
2
3
func()
    for(;i <= 10; ++i)
        for(;j <= 10; ++j)
Имеет сложность n^n, т.е. 10^10 ?

3)Если c = количеству операций во вложенном цикле, то
C++
1
2
3
4
5
6
7
8
func2()
   for(;i <= 10; ++i)
       for(;j <= 10; ++j)
       {
           int a = j;
           int b = a;
           int c = a + b;
       }
Будет иметь сложность 4*func2(10^10) ?

4)
C++
1
2
3
4
5
func3()
   for(int i; i <= 10; ++i)
       int a = i * i * i;
   for(int j; j <= 10; ++j)
       int b = j * j * j;
Какую сложность имеет функция? 3*fucn3(2*n) ?

Кажется я окончательно запутался и пишу бред. Если есть время и возможность, помогите на пальцах понять, хотя бы азы асимптотического анализа. Спасибо.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 19:27. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru