Большая нотация O полезна, потому что это легко работать с и скрывает ненужные сложности и детали (для некоторого определения ненужных). Один хороший способ разработать сложность деления и завоевывает алгоритмы, древовидный метод. Скажем, у Вас есть версия quicksort со средней процедурой, таким образом, Вы разделяете массив на отлично сбалансированные подмассивы каждый раз.
Теперь создают дерево, соответствующее всем массивам, с которыми Вы работаете. В корне у Вас есть исходный массив, корень имеет двух детей, которые являются подмассивами. Повторите это, пока у Вас не будет единственных массивов элемента в нижней части.
, Так как мы можем найти медиану в O (n) временем и разделить массив в двух частях в O (n) время, работа, сделанная в каждом узле, является O (k), где k является размером массива. Каждый уровень дерева содержит (самое большее) целый массив, таким образом, работа на уровень является O (n) (размеры подмассивов составляют в целом n, и так как у нас есть (К) O на уровень, мы можем сложить это). Существует только журнал (n) уровни в дереве с каждого раза, когда мы делим на два вход.
Поэтому мы можем верхняя граница объем работы O (n*log (n)).
Однако Большой O скрывает некоторые детали, которые мы иногда не можем игнорировать. Рассмотрите вычисление последовательности Fibonacci с
a=0;
b=1;
for (i = 0; i <n; i++) {
tmp = b;
b = a + b;
a = tmp;
}
, и позволяет, просто принимают a, и b является BigIntegers в Java или чем-то, что может обработать произвольно большие количества. Большинство людей сказало бы, что это - O (n) алгоритм без вздрагивания. Обоснование состоит в том, что у Вас есть n повторения в для цикла и O (1) работа в стороне цикл.
, Но Числа Фибоначчи являются большими, энное Число Фибоначчи экспоненциально в n поэтому просто хранение, это возьмет порядок n байтов. Выполнение дополнения с большими целыми числами возьмет O (n) объем работы. Таким образом, общая сумма работы, сделанной в этой процедуре,
1 + 2 + 3 +... + n = n (n-1)/2 = O (n^2)
Так этот алгоритм выполнения в квадратичное время!
OpenGL имеет функцию glTexSubImage2D
, которая как раз для вашей цели.
Вот функция, которая изменяет цвет одного текселя:
void changeTexelColor(GLuint id, GLint x, GLint y, uint8_t r, uint8_t g, uint8_t b, uint8_t a) {
uint8_t data[4];
data[0] = r;
data[1] = g;
data[2] = b;
data[3] = a;
glBindTexture(GL_TEXTURE_2D, id);
glTexSubImage2D(GL_TEXTURE_2D,
0,
x,
y,
1,
1,
GL_RGBA,
GL_UNSIGNED_BYTE,
data);
}
С точки зрения производительности, вам может быть лучше сохранить карту локально как свой собственный массив и нарисовать ее на экране как набор нетекстурированных четырехугольников.
Примитивы визуализации сильно оптимизированы, особенно по сравнению с созданием или изменением текстур.